Waikoloa is a nice area for vacationing but not sure that there is much game for fruit hunting. A lot of the more unusual fruit here does not typically make it to market. The best bet is probably if you make it over to Hilo side on a trip. The farmers' market is worth a try, especially if you can make it on a Wed or Sat, the "big" market days. I've heard some people say that there are some unusual fruits at the Kona market sometimes but I have never seen anything very interesting there the few times I visited it. Usually nothing very exciting at Kea'au, Honoka'a, or Laupahoehoe markets the times I have visited them either. I have heard that there is sometimes some interesting fruit at the Maku'u market down by HPP but I have never encountered anything very exciting the times I have been there. Unfortunately, markets can be hit or miss as most interesting fruit is seasonal. Sorry I couldn't be more helpful.
John