Your going at a good pace. Like you said, you have a learning curve so those who have done this several times are going to post faster numbers. Everyone seems to be in agreement that going to Shadow Fang Keep at level 10 is far better than any other starter instance. There are other things you can do to speed it up. The biggest one I can think of is quit looting unless its a boss. Looting adds a good 30-50% to time to level. When you loot then your off to town to sell, then your going back to the dungeon etc. Looting adds a LOT of time to a grind. Also do a search, there are several posts and mentions about going from 55 to 60 in one run of BRD if you get all the quests. I have not done this personally and I have not seen a list of what quests to get to do this but several people swear buy it.

ZF is a popular place at 40 to go to because of the fast pulling you can do while mounted but has its gotcha's with hex, I preferred to hit Stratholme as the pulls are big and I know the place well as its one of my favorite places to hit and its a paladins easy sauce boosting zone with all the undead. Lots of bosses and lots of good lewts.