Pathfinder states that each spell of the Enchantment school as well as each Pattern and Phantasm spell in the Illusion school is Mind-Affecting. See Mind-AffectingD20PFSRD definition and the MagicD20PFSRD chapter for reference.
Mind-Affecting
Enchantment spells affect the minds of others, influencing or controlling their behavior. A mind-affecting spell works only against creatures with an Intelligence score of 1 or higher.
All enchantments, illusion (patterns), and illusion (phantasms) are mind-affecting.
So it seems more like a definition of the Enchantment school instead of the definition of the Mind-Affecting descriptor.
Protection from Evil, as you pointed out does not mention the Mind-Affecting descriptor, but states that:
[...] the subject immediately receives another saving throw (if one was allowed to begin with) against any spells or effects that possess or exercise mental control over the creature (including enchantment [charm] effects and enchantment [compulsion] effects). [...]
If we accept these two assumptions:
- The Mind-Affecting definition does not only refers to Enchantment and Illusion spells (and the Necromancy-tied Fear seems to suggest so).
- An effect with the Mind-Affecting descriptor is eligible to get a second saving throw under a Protection from Evil spell.
Then the answer is Yes.
Note that this answer specifically address your citation of the Fear's Mind-Affecting descriptor. One could also argue that, as long as the Protection from Evil wording is concerned, a Fear actually triggers the abjuration spell's condition outright because - in fact - it exercise influence over the target's course of action.
Intellect Devourer magically consumes the brain of the victim. Once it leaves, there's just an empty hole where the brain used to be.
To quote the monster description:
the intellect devourer magically consumes the target’s brain
Death Ward, on the other hand, prevents the subject from dropping to 0 HP - it drops to 1 HP instead. So while under DW, the Intellect Devourer is actually protected from ejection, if it indeed gets inside in the first place.
Once it leaves the brain has to be grown back in one round, or the subject dies.
"The body then dies, unless its brain is restored within 1 round."
I was about to write how DW would not protect the victim from dying because of a lack of a brain, but then it struck me that as a DM, I would probably rule that "magically removing someone's brain" would fall into the "effect that would kill it instantly" -category which DW protects the subject from.
Mostly because, while the body is still living under the Intellect Devourer's control, there's nothing of the victim left; no memories, intellect, etc.
(Which opens a whole new can of worms in the form of "brain vs soul" -discussion which is open to many interpretations...)
So how DW works in this case (without finding any official ruling on the matter saying otherwise), in my opinion, would be that the Intellect Devourer could not remove a target's brain and enter it, if the target was under DW's protection (which would then end DW and leave the target open for another try, later on).
Best Answer
This is a case of specific beats general :
The general rule here is the description of protection from good and evil that states that the spell has to target a creature. The rules in the stat block of the intellect devourer are more specific and allow the casting in a given circumstance even though it violates the general rule.