Cleon
Legend
Suggestions above all work for me, including Cleon's summon weapon and keeping polymorph. I could see some SR since evasion only works on area effect spells, but it's not a biggy.
Spell resistance would seems appropriate for them, indeed it's curious that the original's stats are missing a Magic Resistance line.
SR = CR+10 ?
It certainly needs some kind of shapechanging power, and polymorph as an X-day SLA would seem to fit - the original could do it 2/day, but I wouldn't mind increasing it.
The Men-Shen also has the ability to become astral at will. This isn't astral projection, but seems pretty key to their duties, since they usually watch over their charges while astral. They also presumably use this power to travel to and from "Heaven".
Maybe we should give them a modified version of an Ethereal Filcher's Astral Jaunt ability, so they can "pop out of nowhere" and attack when physical evil threatens somewhere they're meant to guard?
Something like:
Astral Jaunt (Su): A men-shen can shift from the Astral Plane to the Material Plane as a free action, and shift back again as a move action. A men-shen can also shift from the Astral Plane to any Outer Plane (or vica versa) as a standard action. This ability is otherwise identical with the ethereal jaunt spell (caster level 15th).