Blessing of Kings - This is a good buff, but not fantastic.
It is the best buff in the ENTIRE game lol. :P No other stat buff buff scales at 70.

Since you have elemental shammies in tow you could also think of picking up Improved Seal of the Crusader after you get Totem of Wrath, and then macro them to drop at the same time. With four shaman dropping Totems of Wrath that's 15% crit before any other gear or talents.

If you are going to be doing a lot of instances don't fill out Reckoning. Reckoning used to be amazing until a Paladin stacked it 1800 times pre-BC and one shot Kazzak, it was nerfed less than 24 hours later lol. It's still a decent talent but you don't really need it for damage or threat and it opens up the door to massive spike damage when your attacks are parried by bosses due to the way parry mechanics work in WoW, which is something you want to avoid when multiboxing.

Divine Intellect shouldn't be necessary with the mana you can get back from Mana-Spring, healing converted to mana through Spiritual Guidance and judging Wisdom.

Getting Improved Ret Aura in the ret tree will give you a nice jump in threat and slightly bigger numbers flashing all over your screen.

Vindication is also a moderately useful talent in the ret tree. It is generally more of a PvP talent, the paladin version of Mortal Strike, and doesn't work on most bosses or raid mobs. However, as a general rule it does work on any mob that can be stunned or otherwise CC'ed.

Stoicism is also decent if you have the points and the Paladin is your main toon. Even with 4 x Tremor Totems fear is still the most disruptive CC to multiboxers for obvious reasons.

I am going for a build that looks like this on my Paladin.

Not picking up 5% to parry is a weak spot in the build but I have points to move around and pick it up if needed. What I was told by a friend is that skipping it allows more shield blocks, and thus more shield based abilities to proc, but I can't vouch for that.

I put one point in Conviction just to get to Improved Ret aura. Pursuit of Justice would be great but since my shammies are on follow it would lead to problems with them falling off.

For the Shamans:

You don't need any points in Improved Reincarnation. If you are wiping that many times with four Reincarnations available in an hour ... well you are going to have a big repair bill lol.

The big choices for you are Totem of Wrath vs Nature's Swiftness. Both are extremely good talents. But in your role as PvE DPS I think you will get the most use out ToW. I've been toying with setting one Shaman up with NS so that I have an "Oh crap!" button that macros an instant big heal or for an instant LB to use for a tricky ranged pull but haven't made a decision yet. My main is a resto druid since WoW launched so I am used to having the talent.

The other big choice is in the resto tree. 3% to hit from Nature's Guidance or the nice armor bonus for your Paladin on healing crits. Tough call, but I am going with the chance to hit until I am really geared.

Going for something like this for PvE multiboxing with my paladin on the shamans.

I would change a lot of these talents if I was just tanking or dpsing in a party but I think these builds take good advantage of the synergy between the Paladin 4 X Shaman group for PvE.