Наверное проблема в том, что при UseShellExecute = false параметр verb не учитывается. Попробуйте установить UseShellExecute = true.  Но RedirectStandartOutput тогда работать не будет. Нужно будет придумать что-то другое для получения результатов программы.

В планировщике заданий установите галки "Выполнять вне зависимости от регистрации пользователя" и "Выполнить с наивысшими правами", и параметр "Настроить для..." установите текущую ОС. Тогда должно запустить без вывода окна UAC.

Естественно, если на машине включен UAC, нельзя просто взять и выполнить произвольную программу в обход его сообщения. Иначе, в чем бы был смысл UAC. Как минимум один раз это сообщение должно быть задействовано, либо при запуске программы, либо при добавлении ее в задания. Иначе не работает.

А вообще, для управления службами на удаленной машине наверное нужно использовать не командную строку, а специальный API Service Control Manager. Насколько я знаю, он позволяет работать с удаленной машиной через RPC, если предварительно вызвать LogonUser /  ImpersonateLoggedOnUser с учеткой администратора удаленной машины. См. https://msdn.microsoft.com/en-us/library/windows/desktop/ms684323(v=vs.85).aspx  (но в любом случае удаленная машина должна быть настроена соответствующим образом, чтобы принимать удаленные соединения)