I had the same problem. That boss was one hell of a brick wall, nothing I tried got me close to winning.
Some helpful folks provided me with advice a few pages back and I ended up beating him, though. Go back a little and read those if you like, but the short version is the red orc is extremely susceptible to poison damage. One of Litis' advanced classes (the ones you can swap between using an item) has a couple of skills that can help with that. Sadly, they're multi target so Madeleine has to put on some serious work to keep Kalena alive.
Even knowing this, I lost a few times until I finally made it. In the end even with the poison strat you have to get lucky, there's really not much you can do when he decides to crit Kalena for 100k damage. Take your time getting him to half health and once you do, just go nuclear on him with everyone but Madeleine and hope he dies before you do. It's very RNG dependent, you just have to keep trying until you get lucky.
For reference my team was Litis (used mainly to poison the orc and item duty), Luzfina (spammed her 100% hit rate double hit skill, hoping to land a status effect on the orc), Victoria (just died a lot since she's kinda slow but she did some nice damage with Pyroblast + land burn on the orc) and Madeleine (heal/buff when the orc's above 50% HP, go all in with cleansing, buffing and healing Kalena when he's under 50% HP).
Good luck and be patient.
(So much for keeping it short.)