CapriUni, possibly those are not the first lyrics. According to Claude M. Simpson, The British Broadside Ballad and Its Music (Rutgers UP, 1966),

"The commoner tune name ['a la Mode de France'] seems to have been derived from a ballad 'The French Report,' probably written in late 1942 or early 1643 while the Queen was in Holland raising money and troops for the prosecution of the Civil War. It begins 'Me have of late been in England/Vere me have seen much sport,' and each stanza closes with 'a la mode de France.' No broadside copy seems to have survived, but the verses were included in Rump, 1662, I, 27, and reprinted in Loyal Songs, 1731, I, 25. The eight-line stanza in ballad meter fits the tune, but we have only the refrain upon which to make any confident connection between words and music."(pp. 516-517; s.v. "Nonesuch, or À la Mode de France")

"NONESUCH or A LA MODE DE FRANCE" is also the title given in Maud Karpeles and Kenworthy Schofield, eds., A Selection of 100 English Filk Dace Airs (English Folk Dance and Song Society, 1951, p. 14, p. *47; tune only). There're a lot of CDs containing this tune (Click here); I myself some of them.

~Masato