IMO if you are going to boost a shaman up you may as well boost a group of four new alts (1 shaman and 3 whatever). Use your main paladin like you normally would with instance boosting, and have the extra toons along for the ride giving you the group bonuses. Once you get your boosted shaman to a high enough level, pay the money for a transfer over to your paladin account.

There may be faster ways, but since you said boosting I'm assuming you are going to do all instance runs.