All traffic will be proxied by Cloudflare. This means traffic will arrive at one of the Cloudflare’s edge first. If the resource is cached (images, static pages) then it will be served from there. If the resource is not cached yet or is dynamic Cloudflare will then connect to the origin to fetch that.
Based on that you should consider your origin being closer to both your customer and a Cloudflare POP. For example I have my own server colocated with a DC in Auckland that peers with Cloudflare through one of the Auckland exchanges so traffic between Cloudflare and the origin server is quick.
If you use an overseas server your main users will have quick access to cached content but anything else (in special dynamic content) will still have to go overseas, regardless. So keep it closer to the POP where most users will be connecting to. Also enable Argo Argo Smart Routing | Dynamic Content | Cloudflare
You can use any provider that go through either the NZIX Citylink NZIX or New Zealand Internet Exchange Inc Peering – NZIX
Be aware that Spark does not peer with Cloudflare as per policy so you should not host with a provider that uses the Spark network to your origin.
I am not sure “cheaper data” is always the case. Usually “cheaper data” comes with problems related to customer service, different timezones causing deployment problems, etc.