The Kul’tirans worship fish (technically “the sea”, but envisioning them as a race of Troy McClures is funnier). Not the Light. They do so to such an extent Blizzard saw fit to give them Shaman for some reason.
They are wholly unqualified to be paladins. The Worgen, barely controlled bestial savage half-monsters have more of a basis for it - they at least have a Light devoted Cathedral that’s… actually pretty awesome.