Как вариант: не дублировать меню, а сделать так, чтобы одно и тоже меню было то сверху, то в сайдбаре.
Я сделал ему на том же разрешении экрана display: none, но потом прочитал, что ссылки так прятать нельзя, т.к. из html они никуда не деваются и поисковики видят это и не любят такое.
Поисковики как бы не дураки, они в курсе, что есть адаптивная вёрстка. Если на мобильных устройствах всё будет удобно, то это может даже плюсом стать.
google.com/webmasters/tools/mobile-friendly
А то, что где-то кто-то сказал это вообще не аргумент... Нужны реальные исследования или хотя бы официальные заявления от ПС.
Да и вообще, это же меню, т. е. ссылки на внутренние страницы сайта. Вот если бы вы сотни ссылок на сторонние ресурсы спрятали, да ещё и на каждой странице сайта, вот это уже был бы повод задуматься.