Paladins are the most devote of warriors and only certain Layonara deities actually even have paladins.
LORE is an excellent source of information.
Paladins is a good place to start as it lists those deities that have them and gives an idea as to the mindset of the different orders.
Restricted Multiclassing -
Cleric Paladin and Champion Submissions -
Paladin Spells -
Oaths and Vows
If you wish to make the change then you will have to wait until level 10 when you are eligible for a Character development quest as per the rules for
Character Development quests.
Prior to the GM running that quest you will be required to submit to Character Submissions an updated biography that hightlites your character's progression into the faith as well as link to your current character development Journal where you should be chronically your role play interactions with others of your intended faith and your characters mental and spiritual transition to the intended faith. The character approvers will give you the nod to proceed to a CDQ or point you in the right direction of your role play to get you want to be.
Once you enter the paladin path you may no longer take any more fighter levels. Paladins cannot freely multiclass with anything other than champions (Toran and Vorax) or Undead Slayer (Aeridin) unless it is a Lucindite paladin who can freely take levels in the wizard class (not sorceror). If you wish to take the champion/undead slayer route you may do so with another application and CDQ as long as it is 2 months after your first. If you were heading the Lucindite protector route your RP would have to substantiate learning magic but a CDQ would not be necessary to take wizard levels, just an updated character submission and approval of the character approvers.
It sounds like a long process but really it's not that bad if you keep a good journal and reach out to other players of your intended faith for help in the converting process.
Feel free to ask away with the questions if I missed anything