I'm trying to achieve the following scenario:
How can I achieve this last step? iOS kills the background apps when needed, but is there a way of getting notified when a previously-connected peripheral is discovered? I read something about CB State Restoration but I don't really know if this will solve this situation.
Core Bluetooth state preservation / restoration is exactly what you want. If your app is suspended, it will start you app if a peripheral connects / disconnects or a notification arrives. It is however broken by design in the way that your app will stop being woken up if Bluetooth is restarted for any reason. Examples are Bluetooth crashes (happens every now and then), if the user toggles Bluetooth or flight mode, or if the phone is restarted.