In Medieval times, the Kings were kings by the divine will! They were Kings because It was God will!... 
To say no to religion, is to say you don't have any rights to be king! You are only an oversized armed peasant! ... mmm... maybe in the Mendicant matter this is the most accurate description! 
In the early medieval period, might = right was largely the rule of the day. It was only towards the end when the nobility began to be very broad and the peasantry more powerful that the divine right bull!@#$ was invented.
That's not to say that this isn't stupid. These guys don't want religion in their game because it distracts from the singular focus of conquering everything in sight single-mindedly. Not having religion is a load of horse!@#$ - worship your god-king or whatever, but your characters can't just reject the notion of superstition because "I like my King".
