Leveling has been sped up significantly since BC, unfortunately the starter quests are generally still slow. Once you get past them, though, I tend to find that the boosted XP even without heirlooms, rest or RAF means I often green or grey out zones long before I run out of quests, so it's usually pretty easy to simply skip collection quests.

I agree 100% with Dan about dropping a shaman for a paladin. Being able to drop into dungeons when things get slow is always a good boost, and you can dual-spec the paladin Prot/Holy so you have a tank for instances and a healer for your DK team for dungeons or for either team for BGs when questing gets old. Dungeons and BGs can net you some nice XP when the alternative is collection quests.