Basically, I would do one of two things:
Allow them to be Epic Level Heroes (which is what they might want anyways, just not wanting to say it directly for some reason), but... after you tell them the environment, history, etc... of the land... THEY have to come up with background stories that led them into becoming Epic Heroes already... and you give them all visions that lead them to each other and keep them in the right direction (obviously a powergame)... While fun to play, might be more difficult to DM/manage...
Or, you using the same visions idea... and same environment, history, etc..., just customize the D&D rules... Take off some of the limitations put on D&D (like maximum skill points per level, removing some prerequisites, instead of waiting for a certain level to obtain new ability increases/feats, grant them during gameplay as appropriate/story logical, and/or letting them do things Unorthodox, like, instead of obtaining a new 1st lvl & a new 2nd lvl spell, allow them to give up both for a 3rd lvl spell (1+2=3, LoL)). Put them in a major time event that sounds like it should be in an upcoming Sci-Fi movie (example: humanoids are few and scatterred throughout the land, half killed by unknown plagues, the rest devoured by magical beasts... I'll stop there, don't want to give away all my ideas). Anyway, obviously at first, at lower levels, they won't be able to do epic stuff, but with some of the limitations removed, they should start be able to start doing great and wonderous things earlier than normal (after all, they don't call them legendary heroes for nothing), and if these things help them overconquer a land-wide crisis, they will become legendary... This way is still fun, and easier to manage as well.
Just some ideas.