The variations of the name derive from Llewellyn (more properly Llewelyn) with the first two 'LL's having a sort of 'Hlew' or 'Flew' sound. In English (as opposed to Welsh) settings (some Welsh moved to England after, say, 1450 or so)the tendency was to spell these names phonetically. This custom continued until the late 17th early 18th century. With the development of things, like dictionaries, better education, spelling became standardized. In Great Britain, the Llewellyns (for the most part) seem to have established the "L" versions as proper. In North America, the "F" versions had become common, and continued. An exception I have recently seen is in Wiltshire, in the south of England where there appears to be at least one family of Flewellings. Whether this is a Welsh family long established in the area, or if this is a North American family which went to England some time ago is unknown to me.
In North America, in the South, the "F" version appears to derive from three or four basic families originally appearing (sometimes members of the same family moving from one place to another) in Virginia, the Carolinas and Georgia. From there to Tennessee, Kentucky, Texas, etc. The spelling, "Flewellen" most often appears amongst these families.
In the northern part of the continent, the most common variations are Flewelling-Flewwelling-Flewwellin-Flewellin-Fluelling-Flewellyn-Fleuelling; but they are all members of the same family, descendants of Thomas and Hannah (Smith) Flewelling of Hempstead, Long Island, New York. This family was split by the American Revolution, and the Canadian members are, mostly (there is one exception)descendants of five Loyalist heads-of-family. The American cousins were largely Quaker non-participants. A third, little known branch has traces found in southern New Jersey.
About very roughly 1850 the migratory movements of both sets of families crossed, causing some confusion. For example, in California, without clear indications, it is difficult to determine if a Flewelling/Flewellen is from one of the southern families, or the northern family. Missouri and Kansas families are also problematic. I do know that members of the northern families moved southwards. For example, some branches went from New Brunswick in Canada to what is now Ontario. Later, some went from there to Michigan. At the same time, in New York State, some moved up the Hudson River to the upper state, and then later to Michigan. This, again, creates some confusion. While the Michigan Flewellings are generally members of the same family, the relationship is often difficult to determine. Some progress has been made. This family now has members from Texas to the Yukon, from Labrador to California.
Overall, your surmise the the New Zealand Flewellens came from North America has a high probability of being correct; and the suspicion that the spelling, Flewellen, points to the southern families is a valid beginning point.
My own interest is in the northern family. If you find anything specific about the origins of the New Zealand family (names, dates, places they came from) let me know and I'll see if I can make a connection. For example, I know that a William Robertson, b. ca. 1825, d. 1876,(probably James William Robertson)was the first mayor of Queenstown, NZ, and he was born in the middle of the area of New Brunswick in which many Flewellings were found. The possibility that some Kings County Flewellings also went to New Zealand and were "lost" is very real.