Как можно максимально увеличить шанс того, что поисковик станет выводить навигацию в результатах?
Сделать сайт интересным для пользователей. Тогда они начнут на него ходить. Гугл это просечет и выведет самые ходовые ссылки.
Есть ли что-то из microdata, что "поможет" поисковику подхватить меню?
Нет
Нужна ли микроразметка хлебных крошек, если их нет?
Если какой-то поисковик гарантирует результат, то да. Но обычно вся эта фигня нужна лишь для,
удовлетворения верующих в силу сео и микроразметки заказчиков без вложений в рекламу разделения контента на типы и контексты.
Можно ли оборачивать списки ссылок в блоками и соответствует ли семантике такой код?
Поисковику пофиг. Если юзеры ходят по ссылкам, то сайт поднимается в выдаче, если хорошо ходят по ссылкам, то гугл выводит в выдаче самые ходовые ссылки.
Важно понимать, что к сайту должны быть подключены метрики, чтоб поисковики могли отслеживать переходы.