Where are the backups stored?

Hey same happened to me, there are no backups done by the plugin. You have to create the backup yourself before executing.

Personally I use wp cli tool: https://wp-cli.org/

wp search-replace ‘https://yoursite.com’ ‘https://yoursite.com’

https://wp-cli.org/commands/search-replace/

This plugin is outdated and I don’t think its maintained.