I would make finding a Holy Avenger a multi-part quest. The character does not actually find the Holy Avenger, he gathers the materials necessary to create one and one is made for him, if he is an exemplerary Paladin of his god. The sword could be the amalgam of the shards of several legendary figures from the churches history, all paladins who died serving their god by fighting evil, each piece in the possession of the creatures or organizations that killed the legendary paladins. I would not let a Paladin of less than twelfth level have a shot at achievin this goal, and would make the quests difficult for a group of under 15th level, but hey that's me, after all it requires a character of 18th level to make and a substantial outlay of experience (4,800). Once the materials are gathered I would forego the largest part of the money cost of making the weapon, assuming that the various quests were to get the expensive materials themselves.
As to the mount, I agree with Melriken, pick up Defenders of the Faith, the section on Paladin Mounts is pretty good. As to the specific cat-mount, a unique creature, one that is seemingly the last of it's kind could be very cool, maybe a panther like flying mount or something else with some unusual aspects to it. Why does the Paladin want a feline mount? Of course that's an assumption, you could simply be talking about a feline companion, but becase we are discussing a paladin, I think it's safe to assume you mean mount. His reasons for wanting one might give you some direction in what to do with it.