If you are using AA miles you will need to call AA and pay the phone reservation fee (at least this is the only way I was able to book flights not on AA).

The miles are refundable, IIRC there is a $150 redeposit fee.

You should be able to book using either an All partner award South Pacific to Europe, this will run 45K(Y)/60K(C)/80K(F) each way; or OneWorld Award, for a MEL-CDG-MEL round trip you will probably need the Zone 7 award (20,000-25,000 miles) which will run you 120K(Y)/150K(C)/230K(F). AFAIK, you can't use code shares that are not on a Partner/OneWorld airline (depending on the award type).