I've raised my paladin from level 56 to 64 and racked up over a hundred AA points in Nadox over the last three months (Saryrn server). The best advice I can give toward how to advance your pally the quickest in that zone is to hunt down and kill undead. Lots of undead. It doesn't take long to farm AAs in that zone (maybe an hour for each point if you're solo). If you have (or plan to acquire) a weapon that does proc damage, get all 5 ranks of Weapon Affinity. It will take some time as each rank costs 5 AA points to buy, but it's definitely worth it. Work on Combat Agility and Combat Stability as this will decrease the amount of damage you'll take and raise the amount of damage you will dish out. When you're in your low- to mid-60s, work on the Slay Undead ability. The first rank costs 3 AAs, 6 for the second, and 9 for the third, but, like the Weapon Affinity ability, this will prove well worth it. My level 64 paladin can dole out up to 4200 points or so of damage to undead creatures (the higher level you are, the more damage this ability will do).
Since pallys are primarily a melee class, work on your other combat skills first, then go for the skills that raise your healing capabilities. I know it can get kind of frustrating to farm AAs while you see lower level toons surpassing your own character's level, but trust me, farming AAs will make your character more able to survive the perils of higher level zones.
I hope this helps. If you're ever on Saryrn, send me a tell. My pally's name is Mayce Winnduu and I'm a guild officer in Death Squad. If you want an invitation to my guild, let me know. I'll help you get reacquainted with the game.