How to get this quest
Once you have completed Fortress Of Wrath and obtained the Final Shield quest, talk to Mira in the Adventurer's guild about Richard's anchor.
Getting into the Maid Academy
The academy is the blue-roofed building on the world map. After arriving, you can only proceed further by enrolling. One the the characters in the lobby, Lord Claude, will allow you to do so, but you need to have dealt with Lilim during What Lurks Within The Mountains. Note that enrolling into the academy will make Paulina unable to gain experience over time as long as you didn't complete the quest.
Gaining Maid Score
After enrolling in the academy, the next step is to enter the building where you will get your initial maid score. The initial score is computed this way:
Paulina's also got a maid score which starts at 0 and caps at 0.
The opportunities to gain maid score are:
Reaching 100 maid score will allow you to obtain the letter of recommendation from the maid at the desk. You will after that be able to end your enrollment or continue getting maid score for more rewards (1 magic thread for every 10 maid score beyond 100).
Note that graduating fails the quest and makes you miss a total of 400 experience.
The Catacombs
There is an underground area accessible from two points in the academy. Traveling through this area is the only way to complete the quest without getting maid score. Take the following warning: the battle difficulty of this area is far greater than what you met before if you tackle this quest just after The Hand Of the King.
The catacombs are filled with pollenfog, similarly to the one met during What Lurks Within The Mountains. To get rid of this fog, you need to purify all negative energy points contained in the academy's secret room.
It is important to note that killing Asmodeus will cause you to lose access to the hole inside the maid academy proper, only the hole by the maid academy entrance will remain available. It is recommened to place the rope by this entrance before killing asmodeus, unless the alternate path has been bombed open.
Reaching Asmodeus
Asmodeus is on the academy's second floor. You can access the second floor either from the north wing or the secret room. Sneaking through the north wing requires either Shadowcloak II or 60 AGI. Going through the secret room requires to destroy an obstacle.
Once you reach Asmodeus, a battle occurs. A stronger version of Lilim will fight alongside Asmodeus.
Asmodeus comes with severely weakened stats if you fight him before day 100. His post-day 100 DEF and MDEF are respectively 500 and 600. Furthermore, Asmodeus can recover from the Defenses broken debuff and has a passive skill negating his Light weakness while also giving him resistance to Phys. The passive skill induces an alternating weakness to the Fire, Water, Thunder, Earth, and Wind elements though. Finally, note that your enemies will start with a MATK boost unless you purified the negative energy points contained in the secret room.
To defeat Asmodeu, it is advised to quickly defeat Lilim first. After that, it is best to defeat Asmodeus either with very high MATK or with martials while modifying your melee element to bypass his Phys resistance.
Defeating Asmodeus will lead you to immediately completing the quest. If Paulina's training didn't progress too much, she'll also turn back into Paul.