I get the very distinct impression that if you want to settle steppes and be successful, you need to be able to deal with the steppes nomads.
This is a tough proposition when nomads can sweep in on horseback, raid isolated farms/villages, and then sweep out into the steppes beyond pursuit.
I would think that the Byzantine Empire MIGHT have been able to do it with a centuries long effort - but it would have been tricky. What you'd have to do, I think is settle from the Black Sea to the forest to the north, probably along some river line. Then, when the steppes nomads raid your settled land, send a punitive expedition (probably a largish army of mounted cavalry), wipe out the nomads home bases, and retreat. Repeat a couple of times, and the nomads will learn not to attack WHEN THE EMPIRE IS STRONG. Of course, when the empire is distracted by civil war or war on two fronts, or both, then the nomads will sweep in and wipe out a century of settlement in a few years.
But if they seriously attempted it, they could set up one line. Once it was established, move to the next line, and continue. That way, when a province is reduced to howling wilderness, you can just repeat the whole process.
The other problem is that Greeks, whether Classical or Byzantine didn't have a good suite of dryland agriculture. IIRC, the early Greek settlements were all along rivers and such like, no?
Note that extensive settlement of the North American prairies was far more successful after the coming of the railways. You can't raise cash crops unless you have a way to get them to market - so much early settlement was along rivers (because water transportation is relatively cheap). But there is a strong limit to how far you can drive wagons to market.
Even that amount of settlement FOLLOWED the invention of firearms. Pre-firearms, a peasant might have had a 1% chance of killing a mounted steppes warrior? After firearms, it probably rises to 1:3 or even possibly 1:1, which exchange ratios mounted nomads simply can't afford.
Note that the plains of Russian were ruled for centuries by Mongols, who treated farmers somewhat like livestock and stopped predation on them by other steppes peoples.