I know exactly how you feel and it does take a while for this to sink in. If you are worried you might break the pattern then the main thing you should make sure is that inner layers don’t have a dependency to the outer layers. That is the single most important thing to watch out on. Everything else I’ve written in this article is just a sample way on how to do it on Android.
About the location updates, you are correct in implementing them in an outside layer as a service. Perhaps it doesn’t fit the Repository Patter because you have to register for location updates instead of just calling a method to get it instantly. But you could still have a LocationService interface in your Interactor which, in some outer layer, implements all the Android plumbing for getting a location. LocationService might have a start() method to start location updates which you call from an Interactor. You can then make your Interactor have a callback method like onLocationUpdated(Location location) where you can focus on your business logic. All you probably need for the LocationService is the Context so you can just inject it in any way you want.
I am not sure what you mean about who starts the location service. That is up to your use case. If the user presses a START button then you can go down to the Interactor and make it start the LocationService. You can make it close the LocationService when you are done with your business logic or when a user presses a STOP button.
If the consequence of a use case is a system action it doesn’t change anything! Your Interactor might have a SMSService which just implements sending SMS in an outer layer. The Interactor doesn’t care if the callback he is calling is going to the UI, database, network or an SMS service.