If you call startService() [whether directly or by calling send() on a service PendingIntent], it starts up the OS's process of spinning up that service. The device going to sleep in the middle won't interrupt that process; it will just delay it until the device is awake and running long enough to finish the process of starting up the service you requested.
The only time the service will never start is if there is something wrong with the startService() request itself -- the Intent does not resolve to a real Service definition, or you don't have permission to start that service, or something like that. None of these failure modes have anything to do with wakelocks, though. The wakelock situation won't cause startService() to fail outright.