Paladins are not Priests. News at 11.
Paladins are Knights who are trained in how to wield the Light in a martial sense. Given that the Order of the Silver Hand was in its infancy when Gilneas cut itself off from the Alliance and started building the Greymane Wall, it makes sense that the Gilneans haven’t got Paladins in their ranks.
Their faith, lore wise, isn’t in the Light. They revere the Ocean and the Tides. Meaning they’re more in tune with Shamanism than Light worshipping Paladins.
This is explained in the game. The worgen you play as when you’re a Death Knight is one of Arugal’s Worgen.