How to fix a through hole in a concrete step?
This will be difficult to make it work well. Cement is not strong in tension at all, and what happens is when someone steps on the patch area, the bottom side of that patch will be under tension. It will then crack, and you know what happens. In fact, you have evidence of how it will look. So the best solution is simply to replace the steps.

Assuming that replacement is not an option, I'm just guessing what I would try, as I'm not a mason. Bringing in a professional is the best solution. But you can probably do it yourself. 

You need to add rebar to the patch. See that the steps did have rebar in them. The hole appeared between the members. So, I would start with an angle grinder. Wear a GOOD mask for these first few steps, as a lot of dust will be generated, and this dust is terribly bad for your lungs.


With a wire wheel in the angle grinder, strip off the paint and crud on the edges of the hole as much as possible.
Next, an abrasive cutting wheel in the grinder will cut angled slots in the surface of the hole. (A diamond wheel will also work, as long as it does not hit rebar. Diamond wheels and iron are a bad combination, that can damage the diamond wheel. So I'd just use an abrasive wheel. They are cheap anyway.) The idea is to cut angled slots on each side of the hole, wide enough that you can fit a reinforcing member into it that will span the hole. You want that reinforcement near the bottom of the patch, not the top, since as I said above, it is only the bottom of the patch that will feel tension under a load.
I would also bevel the top edge of the hole a bit with the grinder. Give something for the patch to hold onto.
Rebar comes in standard sizes, the smallest stuff you can find seems to be 3/8 inch thick. For this application I would want thinner rebar, so the slots I need to cut will be easier to cut. As well, I want to get as much reinforcement into the patch as I can. So I might actually start with steel 1/4 inch bar stock, then grind ridges into it to give it some tooth. You can see what real rebar looks like here:





When you do lay the rebar grid into the slots you have ground, I'd next hang hardware cloth (essentially metal screen) perhaps 1/4 inch below the rebar with some wire. The idea is that otherwise, the cement in this patch will just fall though.
Get a high quality cement designed for patches. There are also bonding agents you can put into the cement to help it adhere to the edges of your hole. I'd also add fiber reinforcement (like tiny rebar) into the cement. You should be able to buy this where you buy the cement.
Mix up the cement and trowel it into place. Make sure it gets into all of the cracks and slots. Make sure there are no voids. Feather out the top edges so there are no tripping points, and there is no place for water to sit.
As a very last step, I might dust some sand onto the surface of the wet cement to give traction. You don't want a slippery spot on the step.


If you are not sure how to do this, go into a store that specializes in cement products and talk to the people there. They can help guide you to what you need.