Здравствуйте, Кокин Антон Вадимович!
Вам необходимо объявить переменную для хранения выбранного пользователем способа сортировки (напр. BookmarkOnRange As boolean)
Для замены порядка следования команд меню необходимо его перерисовать, а в коде прорисовки использовать значение этой переменной.
В Вашем случае можно для выбора коллекции в зависимости от виде сортировки воспользоваться оператором Iif.
Для обработки команды меню каждой команде устанавливается свойство OnAction, которое содержит название процедуры, выполняемой при нажатии пункта меню.
Процедура для изменения типа меню должна менять значение переменной BookmarkOnRange и вызывать создание меню заново.


Приложение:
'-----=====добавляем переменную для хранения типа меню
Dim BookmarkOnRange As Boolean
'-----=====

Sub MyMenu()
Dim cb As CommandBar
Dim cbP As CommandBarPopup
Dim cbbTop As CommandBarButton
Dim cbbBM As CommandBarButton
Dim bm As Bookmark

Set cb = CommandBars.ActiveMenuBar

Set cbP = CommandBars.FindControl(Tag:="Restore")
If Not cbP Is Nothing Then
cbP.Delete
End If

Set cbP = cb.Controls.Add(Type:=msoControlPopup, Before:=cb.Controls.Count + 1)
With cbP
.Caption = "Мое меню"
.Tag = "Restore"
.BeginGroup = True
End With

'Добавляем команду в самый верх меню
Set cbbTop = cbP.Controls.Add(Type:=msoControlButton)

'?????????Здесь нужен обработчик!!!
With cbbTop
'-----===== меняем название кнопки в зависимости от типа меню
Iif(BookmarkOnRange, .Caption = "Сортировать по положению", .Caption = "Сортировать по алфавиту")
'-----===== обработчик задается именем процедуры
.OnAction = "ChangeMenuRange"
End With

'Другие команды в меню
For Each bm In ActiveDocument.Bookmarks 'сортировка закладок по алфавиту
'-----=====перебираем закладки в нужном порядке
For Each bm In Iif(BookmarkOnRange, ActiveDocument.Range.Bookmarks , ActiveDocument.Bookmarks)
Set cbbBM = cbP.Controls.Add(Type:=msoControlButton)
With cbbBM
.Caption = bm.Name
.Style = msoButtonCaption
End With
Next bm

Set cb = Nothing
Set cbbTop = Nothing
Set cbbBM = Nothing
End Sub

'-----===== а это обаботчик нажатия пункта меню
Sub ChangeMenuRange
'-----=====меняем тип сортирвки меню
BookmarkOnRange = not BookmarkOnRange
'-----===== и перерисовываем меню
MyMenu
End Sub