But let's do the back of the envelope math. A typical 5G base station would use a couple of KW of power. My guess is they'd use ones with more range, which probably means more power. Let's call it 5kw. I'm not an expert but that seems a reasonable number. Maybe it's a bit high. Maybe it's a bit low. I don't know, I'm probably biasing to too high.
So, if you'd need to power that 24x7 using solar you obviously need some battery and enough solar panels to top those up even on the most cloudy days. If you have a 50kw solar setup, you'd be generating 10x more power than you need on a sunny day for about one third of that day. So you end up with roughly 3x more power than you need at best and probably some reasonable portion of that on average. On a bad day that might drop by a factor 20. So, you need probably at least a week or two of battery to play it safe. If you assume a complete absence of light, you'd need about 120 kwh per day. Of course that's not realistic. So it could be a bit less than that as you always get at least some power. A tesla powerwall would be not enough, a tesla megapack (~2.7M $) would probably be overkill. Probably about a quarter to a fifth of that would be plenty. Probably less.
Not particularly cheap but doable probably. Add a windmill to the mix and you can probably get away with a lot less solar and battery. Probably a few hundred thousand would go a long way and a few tens of thousands would be on the low end of the spectrum. Let's call it 100K per site plus or minus 25% or so. Doing ten of these cost a million. Doing 1000 of these 100 million. Doing 10000 of these a billion.
New Zealand is a 100000 square miles (to stick with your numbers and miles). So, you'd need about 40000 of these things. So a few billion. I bet there are probably multiple creative ways to get that number down a bit. So, not cheap but doable. At worst billions in cost.