Are search engines like Kagi completely screwed by this or is there a way for them to keep operating?

Kagi doesn't have a partnership with Google - they work under adversarial interoperability, stealing results from Google against their will, and paying some third-party to enable this. They'd like to simply pay Google, but Google doesn't want their money.

Kagi is backed by russia so they will be fine.