For some reason I woke up with this thought in my head. Ralph Bashi's animated fantasy "Wizards" would, I think, translate well to the stage. Although there is a little spectacle here and there it is mostly a story of character.
As a straight play, several things leap out at once. The "They killed Fritz!" guys function as a comic chorus, and can play their scenes in one (aka in front of the show curtain or otherwise isolated, allowing set changes). Avatar's "magic" is used rarely and tends towards parlor magic, meaning basic stage magic is appropriate. A pre-recorded narrator could be used -- or a character added, or perhaps Elinore given an expanded part in which she "looks back on" and presents the events she took part in when younger. Weehawk gives an excuse for the fight choreographers to pull out some fun martial arts moves (I've worked a production of one of Shakespeare's histories where the fights were modern martial-arts fests). And Blackwolf's secret weapon on stage is as bald as showing the audience that same projection technology.
Above all, these characters are comic (though also very human) and the lines are funny. For the most part settings can be minimal as the action is moved forward by the fast-moving dialog.
As a musical it is not quite as obvious. I am not a real hand at adapting a work to musical theater. Obviously, one wants to have songs that do narrative work and advance the plot, instead of just filling space (in both the American Musical and in grand opera, the songs almost always work to advance the _emotional_ plot. At the end of an aria, the decision is made towards murder. At the end of a duet, the characters have fallen in love.)
Also, one desires songs that illuminate the inner life of the characters. One would want, for instance, something from Elinore where she can explicate how she does not yet have the confidence in herself to grow into her full fairy powers. And one would really like a little something from Blackwolf, as well!
Obvious choral numbers do leap out; the birth of the twins, for instance.
The one place the assumptions and structures of a musical helps is in providing for a larger chorus. As a stage play, the armies might be small. In the musical, you've got the bodies for some big army scenes, as well as for masses of hostile fairies et al.
The musical structure is also interesting. Obviously, in either adaptation, one wants to reference the original score; I'd call it muchly prog-rock, with a few weepy pop-folk ballads, and much synth keyboards. This works great for the stage version. You'd have to expand musically on it to make up for the lack of visual spectacle in some places, of course.
Question is whether you can develop from that basis to get the kinds of character and chorus songs you want to support a proper musical. Elinore _does_ sing, in the movie. It would seem most honest to the material to have songs of similar style, and not try to break the form too much.
My musical theater roots are showing, tho. I can see the signature tune expanded and adapted into choral polyphony as overture, introduction and narration. I can also see (perhaps the only singing Peace ever does) a "Quintet" number where Avatar, Elinore, Weehawk and Peace all sing about their fears and suspicions and hopes about the journey to confront Blackwolf.