Hi,
Are you using the default posts widget from Elementor, or a custom one via another addon?
Some customizations may conflict with the inner workings of the original posts widget, and the search may not execute correclty.
If you intend to keep the customization, I would probably advise not using the pagination whatsoever, to make sure to avoid this conflict.