I think transiting in Sydney is the only same day departure & arrival option for MEL-ZQN on 15 May. You could ask Qantas to:
- Rebook you on QF151 MEL-AKL 15 May and QF8448 AKL-ZQN (NZ codeshare) on 16 May. You will need to overnight in AKL, worth asking if QF would cover this otherwise possibly your travel insurance?
- Rebook you on QF171 MEL-WLG 15 May and QF8611 WLG-ZQN (NZ codeshare) on 16 May. You will need to overnight in WLG but IIRC the hotels are better value here than AKL, so WLG transit probably better if the hotel stay is on your own dime.
- Rebook you on NZ264 14 May - pretty unlikely to happen unless you get a very friendly agent. If this is your preferred option you could get a refund and rebook with NZ.
- Rebook you on the same direct flight with a date change to 13 May or 18 May