Having them lead an army is an interesting idea. There's rules for it in Ultimate Campaign, and also on the PRD.
In a war, the PCs can only do so much. So managing the army and leading it well becomes part of the challenge.
Winning favor with certain groups would also be a challenge. Being high level only does so much for diplomacy and politics.
Mixing the need for mercy into combat. For instance, they could slaughter a cultist army that numbered in the thousands, more than likely. However, what if those cultists would be harmless peasants if freed from their masters? Maybe killing them isn't the right way to go.
Now eventually you are going to want to get to some combat. Multiple big bads seems to be the way to go. When PCs gang up on any CR appropriate foe, its usually a three-round slaughter. Try sticking 4 CR equivalent bads together, and spread them out. Throw some CR 15 or so "mooks" in to harass them, and maybe mix up your tactics like having an ambush on round 03 where a pile of new enemies teleport in or something.
Change the rules of the game: Have a combat where no one has a physical form, or where magic has a strong chance of going "wild" and having a random effect. Try a "godless" arena where divine magic just doesn't function. Stuff like that.
Environmental encounters: On a plain of the abyss where flight is impossible, the PCs must assault a castle via a ledge that spans a mile-wide river of acid.
Attack their sanity: They have to cross the Valley of Despair, where tortured souls assault them with the injustices and cruelty of life. The PCs have to do more than save, they have to offer hope for every soul that confronts them, or else succumb to that souls dismal world-view.
Traps from hell: Make a hall of traps, and the PCs have to out think them. Be devious. After all, these are traps made by demons.
Gifts that arent: What about a protracted ego-battle with a very powerful, but very strong-willed intelligent item? Maybe one that drains wisdom whenever it wins an ego battle? Yet whenever it does so it grows more powerful, and the PCs need it to have a certain amount of power in order to take on some CR 29 baddie you have waiting for them?
Demon Lords: These are basically CR Impossible, so the PCs can't fight them directly. It's like fighting a god. So the challenge becomes to simply survive the attacks of such a creature for x number of rounds until they can achieve another objective.
Just some ideas.