If you dont care about the min/max approuch then any race will do. As others have pointed out certain races do have some very nice additons that give them a edge vs other races.
Erudite gain +3% Specializetion bonus (translation: More damge, better heals)
Gnomes +10% foci effect and haste items (Translation: More proc Damage, better heals, faster swings *more melee damage*)
High Elf Charm immunity anD Mez resistance (translation: your immune to resistable Charms and haev a +20% bonus to resist resistable Mez effects).
*note Paladins also have Fear Immune AAs so it combos rather well with High Elf.
Those would be the 3 Min/Max picks... Though Gnome and Eruidte are definitely the ultimate Min/Maxer route.
For solid around choice, Dwarves Solid stats and +35% biult in Fear resistance is very nice
I personaly went Froglok, which learn skills faster (not a big deal at the high end but leveling up was nice) and innate swim and bigger lung capacity. Plus you do a kick ass backflip when you cast spells
As to stats... DEFNITELY dump as much as you can in CHA, this still will always be a pain to max out and really helps you land spells (which are key to paladin Aggro). After Cha I would go ether Agil or Dex both are much much harder for a paladin to max out (just look at the top 5). Then again if you dont plan going to the end game ballpark any of your other stats are good save for Int LOL.
If your going to box definitely pick a Healer type to go with you. Healers on SoD are Clerics, Druids, and Shaman (in that order) however unlike Live Druids and shamans don't suck at healing.
For a Paladin I would suggest druid or Shaman over cleric. Druid brings DS and paladins love AoE tanking along with buffs and good DPS of thier own. Shamans bring buffs and slows allowing Paladins to do thier thing.
I feel Druids are a slight better match for Paladins but prehaps thats because Im box a Shaman with mine *shrug*