Measure the axe when you tell a dwarf his hieght
Man, with their stamina and generally surly demeanor toward other races, I'd rank the dwarfs as the ultimate spinning teacup riders.
Legolas has had cause to regret his comments on Gimli's low center gravity and poor sense of balance on many a quest to Disneyland.
Citadel Adbar has a force of warponies, eh?
I wonder if they're trained for subterranean use...
Outside of relevant source material for the Forgotten Realms, I'd rank the wolverine as the preferred mount for any dwarf or gnome who is stout of limb and mighty of mien.
Not only do they have all the rage and digging advantages of Badgers, but they also rank a decent climb score.
Plus there's no sense in riding anything that can't give you a decent fight in a no holds barred wrestling match.
Ah, an important consideration for my dwarf, the original dwarf from the prompt, is that while he is currently based out of Citadel Adbar he is in fact a feral dwarf from Chult and thus might have access to more exotic riding beasts.
For the Paladin I would point out that there is a Celestial Badger, the Mongolian horse did help conquer the world, and you might look at an elemental or celestial boar for the real Norse feel.
I have to say, however, that if I didn't have the feeling the whole party will be underdarking it soon, I would so go with the Elephant idea... ...or better yet a wooly mamoth!!!