I have the same problem. I haven’t implemented a solution yet, but considering three options:
Launch the iOS app on demand and create a mechanism where the Watch app sends a query, the iOS app fetches the results and sends the back to the watch.
Call the MapKit Javascript API from the Apple Watch app.
Use another third-party API like Google Maps, Bing, Yelp, Foresquare, etc.
In the first option, the search would only work if the phone is nearby, which maybe a huge user experience issue.
I haven’t seen a roadmap where this feature is planned for WatchOS, but the Watch Maps app can search so it’s possible this would be exposed as an API in the future.