Возьмем хотя бы мобильную версию гугла. Никакого JS - только ссылки и простая форма (поле ввода + кнопка).
Не нужно целиком отказываться от JS, он просто не должен отвечать за функционал на столько, что у пользователей, у которых отключен/неподдерживается, вызовет проблемы. То есть, для них должен быть "аналоговый" метод выполнения того или иного действия.
В вашем случае, следует использовать обычные ссылки и если так уж принципиально, то при загрузке страницы заменять блок меню на select с помощью JavaScript (т.е, селект будет использовать только у тех, у кого работает js).