Maybe even use a breadstick as a replacement for a club. Cook muffin grenades. Nothing quite says "BOOM" quite like a bran muffin explosive. Give the Ork a chef's hat, too. Maybe replace the furs with an apron that reads "Kiss the mook".
I'm totally Imagining this right now, Its Super Funny Looking! Im imagining Duke Nukem Meets Lord of the Rings, in that breadpunk world mentioned earlier.
In this case, use the Waterworld scenario wherein the world is covered with water rather than land. Small floating cities and ships are what is left of civilization. So your map is not always accurate because everyone is moving around. You have to recruit people for your crew and upgrade your boat with stuff you find, buy, or steal.
Im Really Liking this Idea, I've been working on Village-City Sized Developments. This is Definitely one I have to look into Doesn't Quite fit the original Game play Exactly. But I think it can be done.
And then you beat up Kevin Costner, or whatever.
Id have to stick this in somewhere... It would be too good to pass up.
Usually the safest thing to do when you don't want to tell a 'save the world' story is to personalize your scope. I'm going to suggest a few ideas, and then since I know you guys love to get weird with game premises, surrealize them.
I like your Ideas, I was only trying to avoid a linear story as The Game has a completely open world with various dungeons. Orphan story would work for this, Your (Close Relative?) is trapped in a Magicly Sealed Prison Deep in the (Dungeon? Crypt? Castle?) And in order to break the Seal you must find the Enchanted Keys. These are located in Different places around the world map like Dungeons and Enchanted Forests.
At first, she is very hostile towards the boy. This girl is rough, fierce, logically uncompromising. She has learned to use every part of a situation to her advantage, and is very clever in the means she uses to accomplish her goals. The boy has a young face despite his late teen age. He is polished and refined, but terrified out of his mind when she comes across him.
I like the characterization and character relationship. Nomads are always fun. I may play with this. this would be one Id wait till I could make a first person 3D game though.