well First of,
A paladin is as the cleric, the most devout people to a deity that you would find in the world. Your character would have to have a faith so strong that he would find grace of the deity he is following, for the deity to bestow your char with his powers.
That would require a lot of RP into finding a deity, extensive documantation in a cdj, a cdq, if not more, for taking the paladin class.
It wont be easy if you go that way, but I'm sure, if it`s allowed, it is something that would be quite interesting.
You also have to know that if you are approved as a paladin and pass the cdq. Once you choose the paladin way, you wouldn't be able to take any more levels as a fighter, unless you leave paladinhood through an other cdq.
you can find some information about it using this
link.