I found that hammering him with all the magic a waste of time since it's a waste of MP (or items)
What you can do with Hein is to hit him with all -ra elements at the start of the battle (around turn 1 and 2), take note of the damage. When he starts barrier shift. Take your chance with an element and just analyze the damage afterwards.
If you use Thundara:
Damage is higher than normal - he has Ice resistance
Damage is slightly lower than normal - he has Fire resistance
Damage is really low compared to normal - he has Thunder resistance.
Just keep track of which is weak to what. (Fire is weak to Ice; Ice is weak to thunder; Thunder is weak to Fire)
If you can effectively predict what type he's gonna change to after, add that with knowing everyone's Agility and what turn order they have, you can kill Hein in 5 turns or so.
Just a reminder that he only starts using Barrier Shift when his life is about halfways gone.
I might be a little off with the which is weak to what, but you should get the point of what i'm trying to say here. If you still don't, go play pokemon and learn about weaknesses and resistance.
O yah.. Make your scholars use the items Antractic Wind, Bomb Fragment and Zeus Wrath. They're basically free use of -ra magics. And it owns Hein bad. (looking at 2500 damage if a scholar uses the item on Hein)