How can I destroy the Papacy as a Muslim or Pagan?
The Papacy itself will always exist and be held by the Pope. If he loses Rome he just moves to somewhere else. However, just because you can't rid the world of him doesn't mean you can't reduce his faith to a mere footnote in history. Capturing Rome is a nice start to crippling Catholicism from the outside, but if you really want to feel like you're doing something you probably want to paint the religion map a different color than Catholic White. If you can get Catholicism made into a Heresy, and one of it's Heresy into mainstream, that's even more fun.
Conquest
The best way to convert the Catholic world to the One True Faith (TM) is of course going to involve a lot of conquest. Because of the sheer size of the Catholic world, the biggest aid for the job is going to be a Jihad/Great Holy War CB, so that you can wipe out whole kingdoms at a time, rather than one Duchy at a time with long truces between. And because the AI can get some funny ideas about who to target with your best CB, it helps even more if you are either one of the Islamic Caliphs or the Fylkir of the Reformed Germanic Church, this way you are in full control of who gets crushed and when.
Moral Authority
Both for speed of province conversion, and for promoting Heresy, crippling the Catholic Moral Authority is another good tactic. A full list of effects on Moral Authority is available here but some of the biggest impacts you can make are in Holy Wars and Holy Sites. Every Holy War they lose costs the Pope 3% Authority for 20 years, Every Great Holy War (or Crusade, or Jihad) lost costs 10% for 30 years. If possible, never let them Win a Holy War (or Crusade). If they go Holy-Warring against a third party, you may be able to destroy one side of the conflict with a war of your own, preventing the Catholic from getting a win, or even causing a loss.
Holy Sites (listed here) are of particular importance because the 10% moral authority they provide never fades so long as they hold them. For this reason it's especially good to take those bishoprics away from them. For the Catholic Church, their Holy sites are Jerusalem, Santiago, Rome, Canterbury and Koln. Playing as a Muslim: Jerusalem is Muslim held at most starts and easily recaptured if not, Santiago (in Northern Spain) is usually very close to the Muslim states, and Rome is fairly vulnerable as well, with parts of Sicily frequently being Muslim. Canterbury (Southern England) and Koln (near French-German border) are long shots. Playing as a Pagan, the reverse is generally true with Koln and Canterbury being nearby for most Pagans, Rome and Santiago far away and Jerusalem held by Muslims.
If you really start steam-rolling the Catholic world some odd "Enemy of my Enemy" scenarios can start to pop up. In my own bid for Germanic World Domination, around the time I won the Great Holy War for Germany the Muslims started destroying Catholicism from the South as well. By game end all of the Iberian Peninsula and Italy had been captured by Muslims. Meanwhile the Germanic Faith was in Control from France to Lithuania north of the Alps. The only Catholic King left in the world was the King of Hungary, who was also playing host court to one very sad Pope.
I don't have the proof for that, but I think I read somewhere that the Papacy can't be destroyed. Pope will still reside not somewhere, but in Rome, even if it's Muslim in your game.
There are some way you can harm Catholics even more:
- reduce their moral authority to the minimum by conquering holy places
- this will lead to the spreading of heresies
- allow some heresy to become the dominant branch of Catholicism
- then go for Byzantium and Russian duchies and kick some Orthodox asses)