I think she started out as a cleric, then was changed to a paladin when she became a potential party member and Karlach was re-imagined as a barbarian.
Its one possibility, certainly.
Other one is that Larian just wanted to make sure people get to encounter as many paladins as possible, since they needed to test them properly.
Also ...
