Japanese anime/animated movie where the girl is the key to a world of destruction?

Question

I remember watching this anime/animated movie between 2008-2013 (sorry it's vague) where it's a story about a young hero with blue hair (I recall him being named Spartacus somehow??) who goes on an adventure with his pals and they meet this girl with pink hair (named Nise? Nisei? I think they met her in the desert maybe) and she's really quiet and shy, but she slowly opens up to them as the adventure goes on. Slowly, Spartacus and Nise develop feelings for each other. In the end, the villain (I think it was a sort of witch? or a mature woman?) captures the girl with pink hair because she's the second key needed to open the gates of hell or the gates of a world of destruction (something along those lines), but Spartacus sacrifices himself and ends up saving the Nise girl.

(not sure but I think that in the end, both Spartacus and Nise go to the sky for some reason, as in they leave this realm to save the world and I remember it being so sad because they were leaving all their friends behind...)

I've been looking for it for years with no results, I don't know what to do anymore... If somehow you've heard of a similar story, please let me know...

Answer 1

This rings very heavily of Record of Lodoss War: Chronicles of the Heroic Knight, originally from 1998 but I remember watching in the early 2000's. It also has an incredibly good opening song:

The series starts out with set of characters from a previous series, but later focuses on a new main character:

Spark, our blue-haired protagonist, which sounds a lot like Spartacus:

Spark protects Little Neese, and they develop feelings for each other. Neese contains the soul of Naneel, an old cult priestess, and the villains want to awaken her to cause death and destruction upon the land.

The main antagonist Karla, who's an older witch character:

Karla later offers the heroes the choice to sacrifice their lives and she'll stop her plans that would essentially destroy the world. I don't remember the ending very clearly, but I remember that Spark lives so he ultimately does not sacrifice himself. Neese does give herself up, but through fantasy mumbo-jumbo is able to live.