Thanks for the suggestions everyone. I ended up using concrete and some pieces of scrap wood as make shift forms. I also pushed some concrete back in behind using a broom handle as suggested by fixer1234. Since I didn't want to get wet concrete on the driveway I used a garbage bag and some masking tape to mask off the area surrounding the hole so I could just pour the concrete and push it into place with my forms (you can still see a bit of it left behind in the finished picture).
Some complications/gotchas that I encountered:
1. The pavement around the step wasn't entirely flat, so it was difficult to get the wood forms to line up squarely and stay in place. I ended up putting a couple bricks behind to push them into place and hold them there.
2. The concrete mix I bought was more granular than I would have liked, with lots of large stones in it which made it hard to get a smooth surface.
The fix is still holding well, and I think it turned out reasonable given that I've never mixed or poured concrete before :). Now I'm working on cleaning up all the rust and re-painting the railing.