The paladin is a warrior with strong ALIGNMENT-oriented beliefs (and short of using ALTERNATIVE/supplementary rules, which have the obligation to resolve the confusions, contradictions and issues those alternative rules create, that alignment is LG). They are not special enforcers of a particular deity or religion and their goals are not inherently religious goals as they are NOT any part of a formal religious hierarchy despite possible deep personal commitment to a given deity. Instead they are more PHILOSOPHICAL goals. They ARE blessed supernaturally with special powers and abilities because of their commitment. Even when they gain spells it is as a reward by deities for their longstanding beliefs and faith, not as a part of their job as some kind of religious functionary upholding a particular given deity or religion. The beliefs of a paladin are a personal commitment and it is not necessary to require of others that they adopt their same beliefs. Their goals are otherwise free for the individual paladin to decide - same as it would be for any fighter - given only their commitment to unwavering adherence to LG alignment, and more cautious association with those who are inherently incompatible with their own attitudes and actions. Their commitment is also less towards WRITTEN law as it is a commitment to ORDER (as opposed to chaos/disorder). Paladins, given their singular alignment commitment, have special opposition to evil and will freely exercise their powers against evil as part of their reason for BEING paladins. This REQUIRES that a game setting include societies which accept and even embrace paladins who take such actions or the class has absolutely no logical reason to exist or to have ever formed.
A cleric, on the other hand, is tied intimately with their deity and religion and vastly less with a specific alignment. Between clerics and paladins, it's clerics who are going to be seeking to convert others to their own faith and beliefs. Clerics are the enforcers of their deity's will among that deity's worshippers, insofar as that deity finds it necessary to HAVE their personal portfolio enforced. It is clerics who enforce religious law, lead the combat against religious opposition, and overwhelmingly champion religious goals.