I want to warn you that Paladin decks are usually very expensive to build. There are some Protection Paladin decks that try to combo Blessing of Kings with big ferocious allies like Maiev or Ras'fari and recur them with Redemption.
That won't be as fast or consistant as a Holy Paladin Rush w/ Holy Shock and Twig of the World Tree, but you can build an interesting version of the BoK deck with the new Badge of Justice ring called Renewal of Life to try and discard a few giant allies like The Abominable Greench early to ensure that there will be enough threats to ensure fatal damage when Blessing hits the table on turn 5, 6 or 7. In fact, Blessing of Kings wouldn't even be necessary with the right combination of allies resurrected. Watch out for mages interrupts (Concentration Aura and Antonidas' Aegis help) or Undead heroes eating up your graveyard if you go this route.
If however you would like to focus more on the Paladin hero and less on allies, a good place to start would be Resolute Aura. Stock up on cheap armor with good effects, and work your way up to 7 resources for the Jin'Rohk finisher. Matt Spreadbury made a deck based on this synergy that you can read about here:
http://entertainment.upperdeck.com/WOW/en/news/article.aspx?aid=6382Good luck!

<----WTB Official Obliveron Avatar plz. Viva la Demons!