Es sollte mit Delphi möglich sein einen BroadcastReceiver zu erzeugen.
Dann muss der Dienst nur noch den BOOT_COMPLETED Intent abfangen. (Hierzu benötigt die App die Permission "android.permission.RECEIVE_BOOT_COMPLETED").
Beispielcode und weitere Hinweise (in Java) hier:
How to start an Application on startup?