Ok now my 5 cents. I just can double what tatewaki said.
I always loved the water element for my part, in woq i was the healer in persona.. I had mana enough to keep 10 players alive and yet my mp reg allowed me to never run out of mp.
I tried my waterpriest here and I felt kind of useless cause i've seen Yasira and Hopemed could heal just as good as I could, thanks to the medicine pills that give you full mp every 30 seconds.
So I've made a metal priest and teamed a lot with Yasira and Tatewaki. What Royalite says is right too, up to level 30.
You spirts and bears can't hold any aggro of a mob, but the Paoxiao calls pets from all around and they without exception keep only hitting the Paoxiao. Tate could hit the mobs and they still kept hitting the Paoxiao. Then I turned 30 and got my Zhuyan.. my Zhuyan outdamaged the Paoxiao so every mob around hit my Zhuyan, me, Yasira and Tate could easy kill every mob with some healing the zhuyan every now and then. But the difference from me to Yasira is, that I got +200 more damage on my side.. so when Yasira and me, both killed a mob solo, both had their tanking pets but I killed a mob way faster as she did.
Don't forget we were leveled up to 80 without upgrading our elemental skills. Our Paoxiao's and Zhuyans are still on level 1 of total 5 levels it can grow. If you're level 80 and you Paoxiao's on level 5.. and my Zhuyan too.. we can party and no matter who is in our party, if a metal wizard or an earth wizard, my Zhuyan would hit the mob 2x and gets the aggro until the mob died. So a +defense is useless in that meaning that you just don't need more def, cause you only heal your own pet..
When you choose fire or metal as element on both, priest or paladin you do faster dmg per second or more damage overall, while the priest pet tanks up to 10 mobs same time

Since you can't beat most of the bosses alone a paladin won't solo a lot.. meaning he's in party, mostly with a priest anyway cause of the aura, so the earth element to a paladin makes him weaker in the party, damage wise as if he'd chose fire or metal.
The level 40 paladin skill.. +movement speed mean you only move faster, not fight.. if i'd be +attack speed, then yes, then it'll be something that the paladin could use to get the monster's attention, but not if he's in a party with a priest with his strong pet.