Since you're asking for story research purposes, I'll answer primarily with that framework in mind. (Some of the D&D technical detail will be skipped in favour of plot-relevant information.)
So, the most important part of the answer first:
It depends hugely on who's running the game.
D&D, like most roleplaying games, is run by a game master ("Dungeon Master" in D&D-speak), who is responsible for the world. When it comes to paladin atonement, what is possible is almost entirely up to the DM, according to the DM's sense of the drama of his world. So the answers to your questions depends a great deal on what the character running the campaign would let him get away with.
With that in mind, some typical answers to consider:
A paladin who broke his paladin code on purpose - without actually doing something outright evil - could atone; that's what 'atonement' means.
By the strict rules, a paladin who willingly does something evil can't. (The D&D 3rd edition rulebook read "a paladin... loses all special class abilities if she ever willingly commits an act of evil". Free will matters; if you didn't choose to do it, you didn't break the code. That said, some GMs would have you 'fall' for any evil act, depending on the circumstances.)
Atonement is usually accomplished with the atonement spell, which is a large holy ritual and requires a pretty powerful priest to cast. How much work it is to atone is entirely a dramatic decision made by the DM. (Usually. If the party is high-level, a priest in the party might be able to perform the ritual themselves.)
In D&D 3rd edition atonement reads "A paladin who willingly and deliberately commits an evil act can never regain her paladin-hood"; the purpose of the rite is to give power back to paladins who've broken their code in non-evil ways, or who have done something evil involuntarily or by accident.
That said, this is the kind of thing a DM is very likely to house-rule differently to suit the dramatic purposes of her campaign. Personally, I love fall-and-redemption stories and would definitely ignore that limitation for a reasonably well-motivated character arc.
If the paladin isn't actually sorry, atonement won't work. (A god isn't easy to fool!)
Typically the priest would set some task to accomplish before being willing to perform the atonement, but they don't actually have to - it's just standard practice, to make sure that the paladin really means it.
Example paladin atonement quests: Recover a lost holy artifact. Defend a church under threat. Solve a tricky diplomatic or ethical problem. Make a pilgrimage to a holy site.
Typically the priest would choose something related to the original offence. If the paladin fell by willingly consorting with thieves, for example, he might be tasked to recover a stolen item of great value, or to find a way to recompense their victims.
A paladin who 'falls' doesn't actually lose any character levels; they're still the same basic character. However, all of their paladin powers stop working until they've atoned. (This includes losing their ride; paladins normally ride a magical mount sent by their god - such as an unusually powerful, smart, empathic warhorse. Or weirder things.)
This is a big deal. In D&D a paladin is essentially a Fighter who gives up some of the standard martial abilities of characters in exchange for holy power, smiting evil, divinely granted healing and a whole bunch of other useful special abilities.
So a paladin who's lost those special powers is essentially a really inferior version of the fighter.
Because of this, a paladin who atones normally regains their full prior powers - they never actually lost their level, they just lost access to their special powers. Once their god forgives them, they're good to go.
However, a fallen paladin can't gain new paladin levels until they atone, so if it takes a long time to atone everyone else in the group may be ahead when he finishes. (Also, you can't pick up some fighter levels or similar in the mean time and then go back to being a paladin later.)
Not only can a Paladin go evil on purpose, there's a character class ('Blackguard') that you usually get that way. Essentially, by pledging to a god of evil, the fallen paladin swaps all his Paladin levels for levels in 'demonic ex-paladin'.
This can rather burn your bridges with former friends. Becoming a Blackguard pretty much signals that you don't ever intend to atone.
Just because Andrew's gone evil doesn't mean his D&D character would. Partly because D&D characters can be unlike their players, and partly because Andrew would have to consciously know that he's being evil and choose to have his character follow suit - which he might not.
(That said, Andrew being the kind of person he is, I can easily imagine him having his paladin fall before he managed to do anything really evil in person.)
Also relevant for writing D&D in fanfic:
Edition
D&D depends greatly on which version you're playing. Andrew would almost certainly be playing some version of "Advanced Dungeons & Dragons", but it could be:
1st edition: The original, still used by a hardcore of "old school" players who enjoy the lethality and dungeon-crawling emphasis of early RPG design, and don't mind its quirks. Had almost no clear guidelines on paladin fall and rise, save that a paladin lost his special powers on falling, so the rest would be entirely up to the GM.
2nd edition: Basically 1st with some rules and art tidyup. Very unlikely.
3rd edition: The baseline of D&D play in recent years, and a likely choice. I've assumed this as a default for my answers. (Andrew doesn't strike me as a hang-on-to-the-old-school-regardless player, although Warren might be.)
4th edition: Didn't exist during Buffy air time, so only possible if you're set after series 7. Much more miniature/map play oriented. Not advised for your purposes anyway, since 'paladin fall' as a concept doesn't work the same way.
It's not likely you need to mention explicitly on the page, but just so you know that your answers are consistent with some version!
