That's not entirely true. People in the middle ages ascribed all sorts of mystical magical abilities to saints and their relics. Having priests be able to do something with relics and pray to saints or gods for divine intervention seems entirely in keeping with what might have been expected in the RL middle ages (obviously, flashy things are mostly out, most things should probably be plausibly deniable as actual divine intervention, no matter what the priests claim).
In the middle ages, the religious side and the political side were pretty directly mixed. The fact that they aren't so much in BM (due partially I think to our modern ideas of separation of church and state, partially due to the lack of incentives) is I think a large part of why most religions in BM are fairly meaningless and uninteresting.
To be a pope, doesn't one need to have actually conducted a miracle? (Probably to be archbishop or something, actually).
Sounds pretty magic to me.
