Pally level 61 and 4 Elemental Shammies level 71

Is there any way to boost my pally to 70 with the least amount of time taken?

I tried Mana Tombs and just had my pally on follow for the time being and I do fine in there but the xp doesn't seem worth the effort.

Any suggestions?

I'd ungroup the Paladin and just do quests.
Tag everything, and have the shaman's obliterate it.

You're within 10 levels, so you get 100% of the experience for mobs you tag.
If there's an 11 level or greater variance, you only get the portion of experience of the percentage of damage you deal.
71-61 = 10.. this is not an issue for you.

Quests will be insanely fast, and you'll get 100% of the exp's for kills along the way.
Don't think you'll beat this in an any instance, grouped with 4 toons 10 levels higher then you.

I pretty stuck with quests this evening and got my guy to 63.5 in a matter of about 3 hours. I think I pretty much know which quests I am doing until I get my pally to 68 and then head to Northrend promptly to get him geared so I can WTF own Utgarde Keep and The Nexus.

My only question is maybe I should change one of my shammies to resto to heal and just DPS with the other 3? Seems like the logical thing to do and a resto shammy can heal a hell of alot easier and mana effective then a elemental one.

You could pull an Athene and hope you don't get banned :P

A Resto shaman is a better healer then an Elemental, if you cannot keep the tank up with 4x Elemental.

I'd personally try for all shaman's are elemental, as you have very good offense and enough healing for most content.
In instances, 4x Healing Stream Totem is powerful against a lot of trash. Staggered Stoneclaw totems can be useful, but with a pally they're your Stoneclaw.

Lesser Healing Wave is inefficient, but fast and a quick emergency heal.
Healing Wave is a large heal, especially coming from four shaman's at once.

Resto adds Mana Tide, more efficient heals and earth shield.
Definitely nice abilities.
If you can get by with 4x Elemental, I believe Elemental heals better then Resto nukes.
If you find elemental is not enough healing, go with 1x Resto and see if that works.

Incidentally for leveling, I was using the Kopp outland guide and like that a lot.
His new pricing is pretty sucky, so I went with extremeleveling for questing in Wrath, as one purchase is good for all future updates.

Kopp's older guides (1-60 and 60-70) are available as torrents on www.piratebay.org if you want to try them out.
But if you like them, I'd recommend an actual purchase, just because someone took the time to make them; up to you though.