I believe I had heroed in roughly 73 hours or so. Maybe near 100 tops. As a paladin, you really shouldn't have a problem. In around 100 hours I had all of my defenses, shield mastery, flank attack, angelswing, mace/sword (and I believe disarm, or close to it) perfected, and most of my relevant skills in the upper 90's. Its all pretty easy to do as a shield spec paladin (which I believe you are), so long as you tank and fight mobs that you can take. Get a bard and a voker and you can go from rank 30 to 51 in just a few hours, namely because you should be mowing through most good xp mobs.