All races that can play as Paladins are Alliance, meaning Horde players cannot play a Paladin. As such, faction choice doesn't matter.
Which race should I choose?[]
Humans[]
Humans are excellent choices for paladins. Spirit is an important stat for Paladins since most of them in raids are healers, so [The Human Spirit] is an excellent racial for human paladins. [Sword Specialization] and [Mace Specialization] really help paladins while leveling since these are the main weapons that paladins will use. [Diplomacy] is a quality of life racial that is nice for getting faction gains, especially for endgame factions that will help really well. [Perception] is a good PvP racial for finding stealthed enemies such as rogues and feral druids in Cat Form.
Dwarves[]
Dwarves have high starting stamina and strength, which is convenient for solo leveling. [Stoneform] is a neat racial while leveling and in PvP. Use to increase survivability. [Gun Specialization] is useless for paladins since they can't use guns. [Frost Resistance] is a decent racial in endgame raiding. Many mobs in Naxxramas deal frost damage, so being able to take less frost damage is always useful. [Find Treasure] is a quality of life racial which marks treasure chests on your minimap. While leveling, some of the items that are in these chests can give you gear upgrades. At endgame, this racial isn't very useful.