paladin's give blessing of kings and an aura which is very helpful. DK's have melee haste bonuses and a few other buffs.

Paladins feel more versatile to me but DK's do more DPS while tanking...

My DK tank is lvl 65 and my paladin tank is 80, there are a lot of times where I wished my paladin did more dps, but I wouldn't sacrifice any survivability.

For me it came down to buffs... I chose the paladin.