I haven't run Epic-tier D&D but have run Rolemaster campaigns with PCs in the mid-to-high 20s.
In story terms, my advice would be: don't restrain your players. If they want to conquer kingdoms, or challenge deities, let them. It should be taken for granted that they are among the most capable, impressive and admired (or notorious!) mortals in the land. Prosaic concerns (travel, food, aquiring 50' of rope) should pose no obstacle.
The above advice won't work if you have players who are mostly interested in a power fantasy, rather than in exploring mythic-level play. I don't have any experience with GMing high-level power fantasy, and so can't give any advice.
My own view would also be to avoid too much emphasis on settings like Sigil or (depending how it is presented) the City of Brass, which reproduce all the tropes and pedestrian concerns of Heroic tier play, but with extra numbers and bigger swords to make them a challenge for high level PCs. I think this undermines what is enjoyable about high level play, namely, that the stakes and the backdrop are very different. (Looking at the Planes Above, for example, I'd emphasise the Dominons over the Outer Isles - the latter look too Sigil-y for my taste).
Mechanically, I'd echo what others have said - don't hold back! Unlike Rolemaster, 4e has somewhat robust encounter-building tools, but by all accounts well-build and played Epic-tier PCs are pretty strong. Make them use those abilities.
Some high-level scenarios from my last RM game included:
Flying across the oceans looking for an island containing a portal to the land of the dead. The portal was guarded by a powerful acid-breathing dragon, its offspring, and many trolls, all under water and shielded by illusions. The PCs fought draconic offspring and trolls, and ended up sneaking past the main dragon through its underwater lair and into the portal.
Travelling into the land of the dead and coercing one of the record-keepers of the judgement halls into giving over information about the fate of various mortal souls.
Trapping the Ordainer (a sort of Asmodeus/Demogorgon hybrid), another lesser demon king, and a lesser aspect of Tharizdun inside a dead star which the PCs helped to reignite.
Restoring a dead god to life by having a simulacrum of one of the PCs take the god's place fighting an endless battle in the Void.
I'd also add - I think that it helps the mythic stuff resonaate if the players are actually invested in the values at stake. If the plot is about them fighting a god, give them a reason to fight that god - for example, the god or his/her servants might do something that not just the PCs, but the
players, regard as unfair or improper. In my high level RM game, the players were determined to change things - bring the dead god back to life, trap other gods and so on - regardless of the dictates of karma, and their dislike of the lords of karma had been built up over many sessions where they found themselves on the other side of karma's dictates (eg befriending a banished god, preventing a fellow PC who had wrongly escaped from heaven being sent back to face judgement, etc).
I think the 4e myths have plenty of room to do this - the Raven Queen can be a cruel god of fate, for example, and Erathis and Ioun have all sorts of schemes going on which might get a response from your players.
I don't necessarily agree with all of those who say "start from 1st", but I would at least use some initial sessions to build up some of this stuff. I doubt that it will be enough to say to your players "Here is some backstory - now care about it!".