Paladin and Beastlords make a very potent melee force.
Paldadin has heals and ress, boosted by the Mana candy form the BL, Haste affects both BL and Paladin, Paladins stun is superb for taking aggro, Paladin as Maintank and BL pet as off tank.
Go grab a long lasting KEI on both and u set for several hours of slaugthering.
Only weak spot is pulling. But dont BLs get some kind of animal harmony type of spells?? We used this combo together with me as a monk, and always hunted together, the tree of us and the exp was flowing in :)
Anyways, my 2 cents.