I found Win32::Service, but that only lets you manipulate existing services, not create new ones. A search on c.l.p.m. lead me to Proc::Background which has Win32 support. However, this is just a wrapper for CreateProcess(), which has nothing to do with Windows Services.
I finally found a bunch of Win32 modules (that are not located on CPAN) at the Roth Consulting home page. One of these is Win32::Daemon and appears to do what I want.