Medieval lords and kings weren't born christians since the fall of the roman empire.
Int he late middle ages europe was christian and actively worked together to extirminate pagan population, pagan ruled cities and small pagan kingdoms or societies in for example the nations around modern day litovenia.
The game is set in that period of time.
Still pagan is a big word that spans anykind of noninstituionalized (conflicting)beliefs.
A pagan lord would always cause unrest, even if pagans where accepted by nobility or religious communities.
Unless the pagan lord beliefs exactly the same as the local pagans, which is unlikley.
