Darren, you might want to take a look at the following links and or maybe contacting the originators. Apparently some extensive research (and books) have already been done re the Klee's of France (New Zealand) and they might be able to point you in the right direction. (It looks like the marriage cert for 1st marriage has her born in France. As parents married in Villeparisis, she would be about 3 at arrival, so likely born there..
Klee Family Genealogy Pages http://genealogy.eproject.co.nz/klee_eur/victor_and_emelie.php
Klee family in New Zealand http://genealogy.eproject.co.nz/klee_nz/klee_nz_family_main.php
Emelie Klee http://genealogy.eproject.co.nz/klee_nz/emelie_klee.php
Mother appears to be Emelie Josephine Boulonnois (1847-1884) http://genealogy.eproject.co.nz/getperson.php?personID=I510&tree=Base1 (for which the 1st link has the marriage cert.)
Family History center has 2 available (Both contain links for World Cat)
- Church Records (1668-1792) https://familysearch.org/search/catalog/556506?availability=Family%20History%20Library
- Civil Registers 1792-1885 https://familysearch.org/search/catalog/556533?availability=Family%20History%20Library
- To search online copies of ten year indexes, 1792-1902, parish registers, beginning to 1792, and civil registration, 1793-1885, click http://archives.seine-et-marne.fr/archives-en-ligne (as of 8 April 2009).
P.S. Looks like this might be the "Brother Emile" born New Zealand at Waitati on 28 December 1876
Hope that helps some.