A little tip, never send a paladin into a situation in which Cthulu might be involved. Automatically detecting evil in a scenario like that is like opening up the faucets of sanity and knocking off the valve.
I did once have a friend who's DM ran a strange campaign in which they hopped from setting to setting rolling up new characters and running through most of a normal scenario after each hop.
Inevitably, however, they would run into Cthulu, remember that they had run into Cthulu before, attempt some desperate action, and then be forced to setting hop again.
I believe the scenario would play out a little something like this:
DM:"You walk into the Leanin' Corral bar. Everything appears to be normal."
"I ask the bartender for a beer."
DM: "The Bartender turns around, it's CTHULU!!!"
"'Aaaahhhh!' I draw my pistol!"
DM: "Too late, your world is DOOMED!!!"
This went on until they played Rifts. By that point they were prepared and when they spotted Cthulu slithering through a canyon within Rifts Japan things went a little bit differently....
....Let's just say that with enough Samas powerarmor, Glitterboy battlesuits, full conversion Dragon borgs, and demon hunters the Mountains of Madness can become even more so.