So, under Paladin it says they can get a mount "usually a heavy horse".
So use the base stats for the heavy horse.
And it states that it "functions as a druid's animal companion"
This means that your heavy horse gains HD, BAB, Saves, etc., (all the rest of those modifiers) as your paladin gains levels. Use table 3-8 on page 52 to determine your heavy horse's stats.
Since you are 5th level when you get him, he will have 5 HD, a BAB of 3, 4/4/2 saves, 5 skill ranks, 3 feats, the AC of whatever is in the Beastiary +2, STR and DEX per the Beastiary +1, 2 bonus tricks, Luck, Share Spells, Evasion, and one Ability Score Increase of your choice.
Looking at the bestiary preview the "heavy horse" has very different stats than the "horse" under the druid animal companion sample animals.
As it should be. A horse is the kind of horse you ride. A heavy horse is the kind of horse a man in full platemail rides into battle.
My question is: Does the paladin simply use the basic "horse" stats under the druid sample animal companions and build from there using table 3-8 or would they get to use the "heavy horse" stats from the bestiary and add the bonuses from table 3-8 on pg 52 as they advance in level?
Stick with the Heavy Horse. Since the HD and BAB and Saves all come from table 3-8, you really don't gain that much from Heavy Horse except that it looks larger and more cool, is more likely to carry you and all your heavy gear, and is probably a bit stronger which will almost never matter in the game that much anyway.
However, this is my opinion. The RAW is a big vague on this point and without more clarity in the rulebook, I think a good argument could be made to use the standard Horse entry from the druid list, and some DMs may prefer it that way.
Ultimately it's up to your DM, but if it were me, I would think a paladin in full plate charging into battle on a relatively small riding horse would look silly. And since the game mechanics won't matter much either way, I would go with the horse the paladin should use, the Heavy Horse, especially since it is referenced in the paladin Divine Bond rules.