Please explain why you think a menu should have nofollow on the links?
This seems like a very bad idea to me, see this discussion, especially:
"Google uses links on your site.
It uses them to go from page to page.
It uses them to identify/figure out what they page they link to should be about
It uses them to work out how import a page is in relation to other pages
It uses them to pass link value/page rank between/from/to pages
Using NoFollow without careful thought/consideration can cause some pretty strange behavior!"
I think google knows what a menu is especially if using html 5 nav element around it and I don't think it would be a good idea to put nofollow on the menu links. Seems like you are trying to avoid some penalty for internal links but the idea to put nofollow on menu links seems misguided to me.
You can always add a robots noindex meta to the page from page settings on pages that you really don't want google to index.