Согласны с Вашими аргументами. В указанном предложении верно: службу.

Слово устав пишется с прописной буквы как первое слово полного названия в текстах любых стилей и жанров, напр.: Ус­тав внутренней службы Вооруженных сил, Устав гарни­зонной и караульной служб Вооруженных сил, Устав СНГ, Устав ООН, Устав Пермской облас­ти. Не в начале названия: Морской устав (ист.), Сту­дийский устав (церк.), Транс­портный устав железных до­рог РФ.

В деловой письменности сложилась довольно устойчивая тенденция писать с прописной буквы слово устав, а также слова положение, регламент, постановление и под. в том случае, если они используются вместо полного названия соответствующего официального документа. Но в правилах орфографии эта тенденция пока не облечена в форму предписания, а значит, правилам соответствует написание и со строчной буквы.

В остальных случаях правильно писать слово устав и под. со строчной, например в художественной литературе, публицистике.

Это слова Александра Галича из стихотворения "Вальс, посвященный уставу караульной службы" ("Поколение обреченных"). Слова понятны в контексте стихотворения:

О, суконная прелесть устава -
И во сне позабыть не моги,
Что любое движенье направо
Начинается с левой ноги.

А потом в разноцветных нашивках
Принесли мы гвардейскую стать,
И женились на разных паршивках,
Чтобы все поскорей наверстать.

И по площади Красной, шалея,
Мы шагали - со славой на "ты", -
Улыбался нам Он с мавзолея,
И охрана бросала цветы.

Ах, как шаг мы печатали браво,
Как легко мы прощали долги!..
Позабыв, что движенье направо
Начинается с левой ноги.

И цитаты из устава:

Движение строевым шагом начинается по команде "Строевым шагом ─ МАРШ" (в движении "Строевым ─ МАРШ"), а движение походным шагом ─ по команде "Шагом ─ МАРШ". По предварительной команде подать корпус несколько вперед, перенести тяжесть его больше на правую ногу, сохраняя устойчивость; по исполнительной команде начать движение с левой ноги полным шагом.

Повороты в движении выполняются по командам: "Напра-ВО", "Нале-ВО", "Кругом ─ МАРШ". Для поворота направо (налево) исполнительная команда подается одновременно с постановкой на землю правой (левой) ноги. По этой команде с левой (правой) ноги сделать шаг, повернуться на носке левой (правой) ноги, одновременно с поворотом вынести правую (левую) ногу вперед и продолжать движение в новом направлении.