There doesn't appear to be a GUI-based way of doing this unless you're joined to a domain - at least not one I could find anywhere - so I did a bit more digging and I've found an answer that works for our situation.
I didn't understand what the string representation meant in the knowledge base article, but doing a bit of digging led me to discover that it's SDDL syntax. Further digging led me to this article by Alun Jones which explains how to get the security descriptor for a service and what each bit means. MS KB914392 has more details.
To append to the service's existing security descriptor, use sc sdshow "Service Name" to get the existing descriptor. If this is a plain old .NET Windows Service - as is the case with ours - the security descriptor should look something like this:
D:(A;;CCLCSWRPWPDTLOCRRC;;;SY)(A;;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;BA)(A;;CCLCSWLOC
RRC;;;IU)(A;;CCLCSWLOCRRC;;;SU)(A;;CR;;;AU)(A;;CCLCSWRPWPDTLOCRRC;;;PU)S:(AU;FA
;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;WD)
We needed to grant permissions RP (to start the service), WP (to stop the service), DT (to pause/continue the service) and LO (to query the service's current status). This could be done by adding our service account to the Power Users group, but I only want to grant individual access to the account under which the maintenance service runs.
Using runas to open a command prompt under the service account, I ran whoami /all which gave me the SID of the service account, and then constructed the additional SDDL below:
(A;;RPWPDTLO;;;S-x-x-xx-xxxxxxxxxx-xxxxxxxxxx-xxxxxxxxx-xxxx)
This then gets added to the D: section of the SDDL string above:
D:(A;;CCLCSWRPWPDTLOCRRC;;;SY)(A;;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;BA)(A;;CCLCSWLOC
RRC;;;IU)(A;;CCLCSWLOCRRC;;;SU)(A;;CR;;;AU)(A;;CCLCSWRPWPDTLOCRRC;;;PU)(A;;RPWP
DTLO;;;S-x-x-xx-xxxxxxxxxx-xxxxxxxxxx-xxxxxxxxx-xxxx)S:(AU;FA;CCDCLCSWRPWPDTLOC
RSDRCWDWO;;;WD)
This is then applied to the service using the sc sdset command (before the S: text):
sc sdset "Service Name" D:(A;;CCLCSWRPWPDTLOCRRC;;;SY)(A;;CCDCLCSWRPWPDTLOCRSDRCWDWO;;;BA)(A;;
CCLCSWLOCRRC;;;IU)(A;;CCLCSWLOCRRC;;;SU)(A;;CR;;;AU)(A;;CCLCSWRPWPDTLOCRRC;;;PU
)(A;;RPWPDTLO;;;S-x-x-xx-xxxxxxxxxx-xxxxxxxxxx-xxxxxxxxx-xxxx)S:(AU;FA;CCDCLCSW
RPWPDTLOCRSDRCWDWO;;;WD)
If all goes according to plan, the service can then be started, stopped, paused and have it's status queried by the user defined by the SID above.
Best Answer
That paragraph (and the one you quoted) doesn't make a very clear distinction between the two scenarios and could leave some people to assume that both conditions need to be met.
If you're doing this on a computer that is not domain joined (as in your case) then you need local Administrators rights on the computer in question. No Domain rights are needed or required (naturally because the computer isn't domain joined.
Log onto the computer with a user account that is a member of the local Administrators security group and launch the local Group Policy editor to make your desired changes. Changes you make will be applied to the computer.