Step One: Actually create and level a Paladin, generally considered the least useful of the fighter classes.
Having taken a Paladin to at least level 220 with an alignment of 750 or greater, you can complete this easy, if time-consuming, mark.
First, go to Atlantis, and find the non-PK temple. The master paladin wanders this area. Stay with him and move as he moves. Eventually he'll talk to you when you move into his room. Sayto him yes, and he will give you a letter to take to another paladin.
============================================================================
'Brother, you have learned the ways of the Holy Order of the Paladin and maintained a pure heart.' the master paladin says to you. 'Alyria still cries out as evil permeates the land. Will you accept a quest to help restore the Order of the Paladin and purify Alyria?'
You say to the master paladin, 'Yes'
'Excellent, Brother.' the master paladin says to you. 'The first thing you must always know is that paladins must understand tolerance. The minor Powers did not establish our order to conquer the world... but to save it. We must respect the Powers, though we know that The One is the true path and all that is good is guided by its wisdom.'
The master paladin gives you a soaked letter, sealed with wax.
'Visit our brother, the Grand Master Paladin.' the master paladin says to you. 'He will teach you more of how we can purify Alyria.'
The Grand Master Paladin is on the fourth floor of the Tower of Art. He is behind a locked door. You can bash it open, if you are a monk or rogue, or you can cast magic unlock or knock on it. You may be able to pick the lock but I never tried.
Once you are standing before this mighty figure, give him the letter and he will give you two missions. The first is to kill an easy mob, Meslanesh, who is in Rune Forest just past the samurai duck. Yes, that mob actually has a purpose. Take the lock of his hair that drops every time he dies and carry it off to Mount Vesuvius, to visit an angel.
============================================================================
You give a soaked letter, sealed with wax to the Grand Master Paladin. The Grand Master Paladin looks over a soaked letter, sealed with wax. 'So it appears our aquatic brother has found someone worthy of his technique.' the Grand Master Paladin says to you. 'So be it.' The Grand Master Paladin opens the letter and reads it carefully.
'He has told you we must be tolerant, and this is correct.' the Grand Master Paladin says to you. 'We must also be strong in our own beliefs, and willing to defend it against those who seek to defile it. I have stood as a bastion of faith in this accursed tower for longer than I care to remember, and shall defend the One even with my dying breath. '
The Grand Master Paladin pushes his ring into the seal of the letter, thereby changing it to his own seal.
'You now know another portion of your history brother.' the Grand Master Paladin says to you. 'Take this parchment to the angel who holds the seal of Vyst. In your journey purge the land of a former student of mine, Meslanesh. He has been leading the young away from the True path and deserves punishment. ' The Grand Master Paladin gives you a soaked letter, sealed with wax.
You will have to do this twice. Or, you could perhaps only do it once if you do the next phase first, but I didn't try it that way, so I can't promise it would work.
In Mount Vesuvius, make your way to the Mad Gnome and take the trip deeper under the mountain. Be prepared for the occasional CPK room, of course.
First, you will need to be able to get into Volcanus, so find and kill Wiggles Tenderfoot for the guard's ring. Then you need to kill a goodly priest(yes, as a paladin, the irony) for a shriveled fruit. Take these prizes down to the very bottom of Vesuvius. Give the ring to the guard captain for a militia badge and go north to enter the town itself. Once there, find Mordimus and give him the shriveled fruit. Wait until a glowing red fruit drops. Pick it up and eat it, and you will be teleported. Follow the path to the east until you find Stepha, and give her the soaked letter. She will send you on another mission.
============================================================================
You give a soaked letter, sealed with wax to Stepha. Stepha slides her finger through the wax seal and quickly reads through the letter.
'Ah, that is why you have brought that evil item to my presence.' Stepha says. 'I acknowledge your accomplishment, allow me to destroy it.'
Stepha looks up to the heavens, then glares intently at the lock of Meslanesh's hair, causing it to explode.
'I have stayed on this plane for centuries, guarding against the evil that stirs in the bowels of this volcano and lamenting the state of Alyria.' Stepha says. 'As the Master has said, you should tolerate the beliefs of those around, many are still working through the guidance of the One. '
'As the Grand Master has said: those who seek evil are not working through the One, and need to be stopped.' Stepha says.
Stepha sits down to think about Life, the Universe, and Everything.
'I can tell you that we cannot use evil to purify evil.' Stepha says. 'Using the weapons of our enemies makes us no better than they and as such we must be careful about how we purify the land.'
Stepha says, 'Once there was a master paladin who thought we could defeat the wretched by embracing their ways and he was proven wrong.'
Stepha says, 'His spirit is trapped in the mortal realm and cries out to me in torment.'
'I beseech thee, release this noble warrior from his curse.' Stepha says. 'Bring me the artifact his soul has been bound to that I may release it.'
The master paladin she asks you to find is 'A wraith of a Master Paladin' in Irda Isle Caverns. He is in the NPK area to the east, with the annoying dark paladins and soulless minions. Find the high priest of Azathoth and search in his room for a west door. Open it and make sure you have some form of sense life(detect-hidden, pense, sense life). The wraith will be just inside. He is fairly easy to kill. Take the ankh of malevolent shadows from his corpse and return to Stepha. Give her the ankh and you will receive the mark, as well as the consecrate weapon scroll. There are no other rewards for this mark.
============================================================================
You give the ankh of malevolent shadows to Stepha. Stepha takes a soaked letter, sealed with wax from you. Stepha holds up the ankh of malevolent shadows and whispers to its glowing center...
The shadows begin to dissolve, leaving a glowing blue sphere which radiates in strange pulses...
The blue sphere launches into the sky, towards freedom.
Stepha smiles happily. Things must be going well for her.
Stepha says, 'I wish for you to have this as a token of your accomplishments this day...' For learning the teachings of the Paladin and helping to release our Brother from torment, the Powers have granted thee a Mark. You have been granted the Mark of Atonement! Stepha gives you a translucent golden scroll.