Yes, I think you’re right: your best option is to transfer your Velocity points to KrisFlyer as that will maximise your options.
As a general rule, if you’re not sure how to search for Star Alliance availability, the United Airlines website is a good place to start. I don’t know the dates you want to travel, but I just chose November 2018 at random and did a search, and there’s good availability – not necessarily with ANA, though, so you might need to stopover somewhere in Asia on the way.
Once you’ve found your flights on the United website, you could see if they’re available for online booking on the Singapore website (click on “redeem flights” and, if you’re not flying Singapore Airlines, “Star Alliance Airlines”); if they don’t show up but you know they’re available from your United search, give Singapore Airlines a call and hopefully they’ll be able to book your flights over the phone.
All the best with your trip!