I have a Windows program that installs a service.
I need to edit the HKEY_USERS registry key, however I am unsure if it is possible for services to do so.
Yes. They can. As long as they run under the SYSTEM account.