You can modify the level requirement for being able to change a hero's name in the globals.gpl file in Steam\SteamApps\common\Majesty HD\SDK\OriginalQuests\GPL and editing the field
to reflect the level you desire to change their names at.

Adding and editing the built-in name generator is not possible, but it can be circumvented. You'd essentially have to compile First/Last names into a list for each hero, then add or edit them as you see fit and then have the name generated for the hero once they enter the map.

This method is incredibly time consuming, and it is something I intend to tackle at some point, but it essentially boils down to most of the effort involving training hundreds of heroes and then typing out all different First Names and all different Last Names. The upside of this is that you can essentially put in name generators for additional custom heroes unique from the original ones in the game, but it mostly comes down to whether you'd feel its worth the effort to go through in the first place.

Oh, awesome, thanks. I've got a list of first and last name additions for each hero category that I'd like to figure out how to implement.

Small follow-up: is there a way to modify the character limit for custom hero names (that is, name changes made in-game)?

I wasn't aware there even was a character limit. I've only ever used the function in the code to modify names for things, and with those you basically have no character limit, though it would be obtrusive having a name stretch from one edge of the screen to the other.

Edit: Just tried it out, and that is a very strict character limit for typing it out in-game. I can say with definite certainty that using a function definitely bypasses the character limit.

What functions are you referring to? How does one change the hero's names?