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...