So many things wrong here.
First, leveling doesn't grant additional spells until praying for an hour. If Forgath leveled up while fighting Kore, he should have needed a rest break to gain his new spells.
Second, the whole trip recovery wasn't true to the game either. If you're tripped you can either stand as a move action that provokes an attack of opportunity, or crawl 5 feet which provokes an attack of opportunity.
Bah, silly realistic combat getting in the way of my 3.5e rules.
Hold Person prevents you from taking actions, and also paralyzes you. A successful save breaks the effect. There's no way that Kore could both have been able to cast Remove Paralysis, and needed to.
I think the trip recovery was another of Kore's gadgets, to compensate for his superheavy armor that didn't allow very good movement. Forgath should have gotten an AoO but he had backed off out of smashing range. I always notice when someone in a fight scene just stands there not taking advantage of his opponent being prone / dazed / etc. It's just dumb.
As for the Remove Paralysis, I totally agree. He said the words for Remove Paralysis, so even if it was a voice-activated magic item, he still wouldn't have been able to move his lips to make the words.
Also if Forgath went up a level it must have been because of an ad hoc XP bonus for completing the objective of entering the door or perhaps solving the puzzle. I figure if the DM is doing XP awards for puzzles he probably has his own rules for leveling up. Although I don't know how many DMs allow leveling up mid-fight. I would think for paperwork reasons you'd at least have to finish the fight.
And why did Forgath have to wait until level 4 to use Hold Person? You get access to 2nd level spells at 3rd level Cleric.
Finally, they sure have gimped Hold Person. In 2E you get up to 4 people targeted, with save penalties if you focus down on fewer targets. It also lasts twice as long, and doesn't allow saves to break the spell once you failed.