I got a free hero at 400 Fame as expected. I then bought some Henchmen, taking my Fame below 400. The UI then says you will get your next Hero at 400 Fame. Fortunately, you don't, and when it gets over 400 again it transfers to saying that you will get your next Hero at 800. So it is a very small flaw in the UI.

The Henchmen for Men are pretty OP I think. I am currently building Henchmen that cost 0.4 Gold per turn to pay, and take 60 off the Unrest. If I need to, I can also build them so they take 30 off unrest and also make 5 gold per turn. Or do research. The only limit is the amount of Fame you want to spend, but once you get to, say, 400, that is 20 pretty impressive governor types.