primordial paladin

[(Psi)SeveredHead]

There's a similar character class, either a paragon path or a theme, in the Dark Sun book. I think it's called Primal Defender or Wild Guardian.

 

[Mentat55]

Primal Guardian is the theme from Dark Sun. Primal power source, defender role, some good elementally themed powers.

Divine Power has the Elemental Challenge feat, which lets the paladin do elemental damage instead of radiant damage with his divine challenge. Plus there are a fair number of paladin powers that do fire, thunder, or cold damage, though I am not sure they are the best powers for a paladin.

 

[Wednesday Boy]

There was an Unearthed Arcana article that discussed atypical deities for a PC to worship and touched briefly on worshiping primordials. (Dungeons & Dragons Roleplaying Game Official Home Page - Article (Strange Gods)) In it they have an option for runepriests to exchange their healing rune for an resist elemental damage rune.​