Yeah all those sound like good ideas.
I only went with mute because it would get rid of the problem of finding a voice and in a medivil type setting it would make him the ultimate underdog. Mutes were not treated well back then.
I think it would be important to make the bond between him and Zelda as strong as possible so there would be something at stake the viewers could relate to and there would be a good reason it was called The Legend of Zelda. It should be her story too.
I agree Link should be the ultimate do going hero like Luke Skywalker or Robin Hood.