The paladin has some awesome heal capabilities. Hand of sacrifice one, beacon another, heal a third and potentially BOP the 4th to reduce damage party wide... takes some proficiency but they also put damage absorbion bubbles on their heal target for free. Sure they are mostly single target healers but with some good mouse over macros they can and are awesome. My main is a HPally that I pretty much only RBG on and most of the time even when stuck being a tank healer I am close to the top healer in raw numbers (dang you Restodruids!!!).

Finally, the benefit of paladin is they are as fast as your DKs. Get them there fast as opposed to slowing down for Resto Shammy/Priest.