UPDATE:
- Первая проблема заключалась в том, что я использовал .jar, а не .aar (сгенерированный из android studio), .aar также содержит AndroidManifest.xml (.jar нет), поэтому Unity может объединить все Манифесты в один. Без манифеста его сервис не указан в финале AndroidManifest.
- Вторая проблема заключалась в том, что я поместил свой .jar в пользовательскую папку в /Assets/Plugins/Android/my_folder/my_plugin.jar, и он должен быть в /Assets/Plugins/Android/my_plugin.jar (только с расширением .aar).
После всего этого мой сервис входит в метод onCreate (унаследованный от класса Service), но сразу после этого вызывается onDestroy (также унаследованный от класса Service).