Ive made an override for this, however that would also disabled it for a paladin which you don't want to.
If you have a NWNX_Funcs, and you have afaik, you can use RemoveFeat/AddFeat method. For a new character, remove horse menu (feat id 1089). And in OnLevelUp event, check whether character has five or more levels of paladin, and if does, whether he does not have horse menu and in those cases add it via NWNX_AddFeat or HorseAddHorseMenu(oPC);
Also, if you are using x3_mod_def_enter script in your module, uncomment the line "HorseAddHorseMenu(oPC);" there.