Several possibilities, I think this covers them.
* A complaint was made and he was charged with rape before Dec 1
* A complaint was made and no charges had been laid before Dec 1 but were laid after he was arrested and charged with murder.
* A complaint was made and charges laid after he was arrested and charged with murder.
I think the third is by far most likely.
The trial will be very important for his attempts later at parole and almost all his future travails, and it is hard to see how such a trial will work in the NZ context. I guess imagine this mess in Scotland or Ireland for comparison.
Firstly, it doesn't strike me as a mess at all. It's far from uncommon in high-profile cases for other alleged victims to come forward on account of the publicity related to the first trial (sometimes these latter accusations are untrue, sometimes they're true....), and for the person on trial subsequently to go on trial a second (and even third or fourth) time on charges arising from these later accusations.
In particular, we've seen lots of this around the whole "metoo" movement and around investigations/trials related to historic sex offence accusations. And very often, the defendants concerned are well-known public figures. While it's clearly not wholly desirable for, e.g., Rolf Harris to have gone on trial again on additional historic sex offence charges, at a point when I'd venture to say that every single adult in the UK knew very well that he'd been convicted on several similar charges in his first trial.... this is the point when the judge's instructions to the second (and third, etc) jury are absolutely critical: the judge must compel the jury, in the most severe terms, to assess the defendant's guilt or non-guilt purely upon evidence and argument put to them in this particular trial, and not to let their opinion be coloured by knowledge of the outcome of previous trials (although E&W law increasingly allows - under very strict circumstances - for "similar fact" evidence to be introduced to indicate a pattern of repeat offending).
So I don't see any particular issues around the man who's just been convicted of Millane's murder subsequently standing trial again on fresh criminal charges (provided, as I said, the trial judge directs the jury explicitly and firmly).
And also, I'm not sure what you mean by "The trial will be very important for his attempts later at parole". This man is 100% guaranteed to receive a life sentence for the Millane murder - the only issues to resolve are a) whether - and if so, by how much - any psychiatric reports or other issues contribute to an adjustment in the number of years he must spend in prison before even being considered for parole. But that number of years is effectively certain to be well in excess of 10.
So the issue of parole has zero short-term (or even medium-term) relevance here. The only issue in which his near-term release from prison would be relevant is around any appeal he lodges, and if he's subsequently granted leave to appeal. However, I'd say that even if this happens, there's also virtually no chance that the Court of Appeal would grant him parole pending his appeal being heard. Furthermore, I'd say that even if he's granted leave to appeal, and his appeal successfully quashes his conviction in favour of a retrial, there's still a very low chance that he'd be released on bail pending such a retrial.