My theory is that the original idea was to have [Illithid][Wisdom] aka using a tadpole, which transmuted into [Paladin][Wisdom] when devs were copy-pasting their code.

Or they've just copied and pasted from Cleric!
It didn't occur to me during my paladin playthrough that it should be a Charisma check for a paladin, but now you say that @Melivy, of course it should!