я так понимаю делать перерисовку меню каждый раз через метод, наследуемый от qwidget repaint()?
Нет средств там для изменения порядка кроме как создание пунктов меню последовательно по определённому порятку.
Поэтому тебе надо будет для изменения порядка пересоздавать меню.
При этом QAction —ы из которых состоит меню, пересоздавать не обязательно.