Custom search with check boxes

We are migrating from a custom CMS to multi-site WP.

One of our web sites needs to have a custom search:
User selects a Location / type / type2 / type 3. These are 4 sets of check boxes. Once selection is made and search button is clicked, pages have to be searched with the selected criteria and displayed.

Pagination if selection results in multiple pages: say 5 results per page.

Currently the data for all the criteria is in tables, an SQL is built with a where part and resultset is shown.

I would prefer to have a plugin do the above. Is there such a plugin available?

I am open to non DB search, as the resultset pages exist in WP pages.

Any advise ?
Thanks in advance,