I have some ideas but you guys are very creative and I'd love to get some advice:
In our last campaign on this homebrew world, an elder evil popped up, devoured all magic and almost ate the world. The heroes saved the day, ascended to godhood.
Its been 800 years and magic is still gone. I want it to come back, any ideas how? And how do you think the heroes should discover it?
What are the details behind the heroes saving the day? What happened to the elder evil that devoured all magic?
I ask, because depending on how it was defeated / destroyed could lead to a flavorful way of it coming back.
You'd think meaningful godhood in PF requires the existence of divine magic. Do you just mean arcane magic?
Either way, perhaps there's some relics of the ascended heroes which have been kept in temples for the last 800 years (signature weapons, etc.), but now a heretical thief/band of thieves has stolen and experimented upon them. Strange magical occurrences are popping up around the thief's path and the players have to deal with them as they chase down the thief/thieves to recover the relics.
Or perhaps the barrier breaks with the arrival of people from other stars on vessels they name 'spelljammers'. They might be friendly traders, raiding slavers, or invaders, but in any case the upheaval they bring is nothing to the upheaval of many people suddenly being able to use magic.
It might simply be a magitech breakthough. Some genius works out how to work magic depite the elder evil and naturally, their allies/ruler decides to use this to try to achieve political goals by controlling the flow of information. Spy vs. spy followed by possible military action.
I would use real world analogues and then pump up the idea to ridiculous levels. Like you know how you sometimes smack a machine that doesn't work and then suddenly it does. Just give the world/the laws of physics/history/the gods/narrative reality/ dreams / that elder evil /whathaveyou a good wallop! In other words, before you make things better, make things worse.
For instance, after 800 years none but the eldest elves still remember magic themselves, hazily, their memories covered by the mists of time. Their stories are wondrous, beautiful and horrific, all at once, but to most folk they're still just that: stories. Most have long since stopped believing it was ever real. Even some of those ancient storytellers are starting to doubt themselves, questioning their own sanity. Then one of them snaps under the pressure, recalling sorcery's sanguine origins. Yearning to see magic once more before his end, desperately he crosses the line into evil, experimenting with all manner of people and blood. Time was, so he paradoxically reasons, once, magic could have stopped him, so now nothing can stand in his way of recreating the means by which he hopes to go.
Ancient elven high level 'mad scientist/doctor' as your big bad (vivisectionist alchemist perhaps?). The campaign starts with the characters trying to solve a case of a single missing person, but the numbers soon swell. Horribly mutilated corpses and such are found. Eventually a pattern emerges that allows them to identify the serial killer and the hunt for this elusive maniac begins, but at the same time the characters themselves become prey. Finally, the confrontation! The villain explains himself, revealing not just the exact truth of his actions, his methods and motives but also his results! He's actually succeeding... He flees, of course, to continue his experiments elsewhere.
Will the players choose to save magic or people? Once the choice is made can they do it in time (the answer should be "NO!" either way, just FYI :p This isn't the finale yet!)?
After his success the BBEG changes his modus operandi. After all, he has his answers, so no longer needs to kill. Instead he injects people with sorcery causing chaos to follow in his wake as normal folk don't know how to handle the new situation, creating yet more difficult obstacles for the players to face before they can finally confront him and bring him to justice.
I'm now going to write this out some more :p I like this campaign idea!