functions.php / replacing div’s with new ones?

I would definitely suggest you rewritting your theme.

Correct me if I am wrong, but WordPress themes are created so that you can manipulate with them. (if you want)

Another thing to take into consideration is, assuming from your filename headerstyle3, you probably have a theme containing more of such pages, varying in numeric index (headerstyle1, headerstyle2), with a different design, so remember to deal with them also.

Please, bear in mind, that I can not tell you, how to replace your code. In order to do that, you need to provide us with a little bit more info, (like whether you want us to help you replace it), i.e. the whole source of your desired menu, your current file content of the file headerstyle3…