Buenas
Podrías usar links alternativos dentro de los tags <noscript></noscript>
De esa forma los dispositivos que no soporten javascript leeran el contenido, supongo que eso incluye a los buscadores. Así además tendrás un sistema de navegación alternativo en caso de no activarse el menú javascript por estar desactivado o no tener soporte
Un saludo