There are a few ways:
- A Paladin can exchange the Warhorse for something more powerful, various Sourcebooks have alternate Mounts(some are able to change Shape, but I doubt even one of these is availible by ECL 8).
- Alternate Classfeatures, again various Sourcebooks(IIRC Dungeonscape has the 'Underdark Knight', which is one of the better ACF's for a Paladin)
- A Custom Item based on Alter Self is around 12.000g and will allow any Medium to Huge Magical Beast that has 5HD or fewer.
- Some Paladins(of Mystra, via Sword of the Arcane Order) could, of course prepare Alter Self(and later Polymorph) from a Spellbook and cast it at the Mount.
- Somehow get Arcane Spells(dipping into Bard and taking Devoted Performer can work, if you have the Int Duskblade is even better. Mystran Paladins can get into Knight of the Weave PrC), use an Eternal Wand of Alter Self and share it with your Mount.