Cool! I bet you're right about a waterproof over-coat or primer preventing staining.
The person who suggesting painting cinder blocks said that she used regular indoor latex paint, and even diluted it with water! It seemed to me that that would soak in so fast you would need many c oats, but she said "no". I think she was only changing their color from beige to sand.
I'm definitely going to change this wall with 1-2 courses of cinder blocks along the bottom, and probably run the pavers the "short way" along the top.
The only downside I see is that my yard is so small that the (6"?) width of cinder blocks will consume 6 times as many square feet as the 1" or 3/4" thick pavers.