I'm fairly sure that you can't auto da fe pagans, and that that's intentional.
Remember, "Pagan" doesn't mean "follows some peasant belief system." It means "follows a belief system that is not presently represented among the officially-founded religions of the continent," or even "hasn't yet bothered to/been able to sign up at a temple for the officially-founded religion on the continent he/she actually follows."
So they could be someone who is, in fact, a follower of a religion you would consider a variant, but no one's officially founded that religion on the continent you're on.
Auto da fe is for removing an enemy of the faith, not just "someone we find inconvenient."
As for the rest of the confusion...chalk it up to inherent drawbacks of the religion system, so far as I'm concerned.
