I'm not able to reproduce this problem when using browser.storage.onChanged from a background page, it works as expected for me there. I copied your sample code verbatim. Are you seeing this failing when registering the event handler from some other context (e.g. from an injected content script in other extension content like a popup)?

Sorry, there isn't a way to add additional search engines to the Search engine: setting in Safari's Search preferences.