I have a front porch/patio and back made out of pavers surround by large concrete blocks. Sometimes, the edge blocks come loose, especially here which is a very high traffic area. I think the lip probably acts as a little bit of a lever too. In the past I tried repairing another one with construction adhesive but that got a little flexible when it got warm and the block levered right out when I stood on it. For this step we tried mixing cement, cleaning it out and resetting the block (also kept it dry after repair, no walking on it for a few days). But after a little less than a year it's out again.
If the mortar or cement bed that was bonding the block in is too thin, the setting bed will dry out too fast and make for a very weak bond. Cementitious products need to cure slowly, by keeping the product damp, not wet. That is a delicate balance for some products, since even too much dampness can cause the cement or mortar bed to get too wet and creep back out, not filling the gap as it should.
My suggestion would be to use a modified thinset, it can go down real thin where needed and is quite sticky, so controlling the mess can be quite a task.
Make sure the area where it is applied is really clean, lots of water and wire brush, using a chisel and hammer to clean out lumps that may affect how the block goes back in, "Dry fit" the block first, insuring the block will go in lower than the surrounding area by 1/8"-1/4". If the block does project over another surface, it would be wise to add something under the projected end so it settles in at the proper height, and does not allow the thinset to run out, creating a void in the bond. The thinset, when it is mixed, needs to be the consistency of peanut butter, apply a thin layer to both the block and the pocket where it will go in. I seen the joints are really tight on the sides and back so gauge the layer accordingly on the back, the sides should scape off any excess as it goes in.
You may want to use duct tape to mask the areas where the ooze may occur, then again it may get under the tape in some cases anyway. You can use a sponge to clean it up, but you absolutely MUST use a sponge that is squeezed so hard it hurts doing so, there cannot be no more water added to the thinset, or it will run out of the joints like a river that cannot be stopped. Keeping the duct tape intact will aid in keeping added moisture down. Still use a nearly dry sponge, if needed step on it in an area away from the work space to allow other pavers away from the area to soak up more of the excess water.
The last requirement is use a thinset that is approved for exterior use, it should not be hard to find. Your choice of colors are either gray or white.
Uh, I would use mortar rather than cement. Cement is used in concrete, grout, and mortar, but adding things to cement improves its abilities depending on the purpose. Grout goes between blocks, bricks, and tiles as a filler. Mortar on the other hand has lime which effects the bonding strength. There are a bunch of different types, and I've only worked with thinset and the stuff used with tuckpointing, but presuming there aren't structural issues at play, it might get you what you need. Here's an article talking about types of grout and mortar.
The second and third pictures clearly show that the block is cantilevered over the step below. That's the root of your problem, as far as I can see.
Solutions are various. You could take out more pavers (and add more large blocks) so that the large blocks turned 90 degrees to this arrangement are lengthwise to the step, with proportionally smaller overhang.
It appears from the pictures (but that might be a lie) that the distance to the step below is small, so you could fill in the entire space with mortar so that the step is solidly bedded all the way to the edge, rather than hanging over as a cantilever.
You could remove all the edge blocks, and form and pour concrete in place to replace them.