Greetings,
The only way to get PvP status removed is to /petition for it, as a previous poster mentioned.
What normally happens then is that a Senior Guide or GM assigns you a level-appropriate quest to complete. Once this is done, a GM will remove your PvP status.
The other poster who saw a Paladin on a quest more than likely saw him after it had been assigned by a Guide/GM. As far as I know, and unless there have been major changes, there is no in-game quest to remove PvP.
Depending on your level, and the availablity of Guides and GMs on your server, you may be quicker deleting and starting again after dumping all your gear in the shared bank, as Cobra mentioned.
Hope this helps!