You could us the 'net use' command:
var p = System.Diagnostics.Process.Start("net.exe", "use K: \\\\Server\\path");
var isCompleted = p.WaitForExit(5000);
If that does not work in a service, try the Winapi and PInvoke WNetAddConnection2
Edit: Obviously I misunderstood you - you can not change the sourcecode of the service, right? In that case I would follow the suggestion by mdb, but with a little twist: Create your own service (lets call it mapping service) that maps the drive and add this mapping service to the dependencies for the first (the actual working) service. That way the working service will not start before the mapping service has started (and mapped the drive).