The embedded story in Apuleius, Metamorphoses IV.28–VI.24 (the so-called 'Tale of Cupid and Psyche') has elements of a fairy tale. It's referred to as belonging to the category of narrationes lepidae anilesque fabulae and begins like this:
erant in quadam civitate rex et regina.
There were in a certain city a king and a queen.
The indefinite quadam civitate has, I think, the same sort of distancing effect as 'once upon a time' does in English, though in space rather than in time.
Another story that opens with such an indefinite – though of identity instead of either time or place – is the story of the widow of Ephesus in Petronius, Satyricon 111–112. This story has elements of a folk tale at any rate, if not of a fairy tale, and begins like this:
matrona quaedam Ephesi tam notae erat pudicitiae ut vicinarum quoque gentium feminas ad spectaculum sui evocaret.
At Ephesus, there was a certain matrona...
Another significant feature that is shared by the opening of both these stories is that the main characters are described as somehow more than human. One often finds this feature in, e.g., the tales of the Brothers Grimm. In Petronius, the widow has 'such marked chastity that she drew even the women of the neighboring popuations to the spectacle that she presented.' In Apuleius, the second sentence of the tale describes Psyche (and her sisters) thus:
hi tres numero filias forma conspicuas habuere, sed maiores quidem natu, quamvis gratissima specie, idonee tamen celebrari posse laudibus humanis credebantur, at vero puellae iunioris tam praecipua tam praeclara pulchritudo nec exprimi ac ne sufficienter quidem laudari sermonis humani penuria poterat.
These had three daughters, conspicuous in their beauty; however, although the elder daughters were of pleasing appearance, still, they were believed capable of being suitably celebrated by human praise. But the prettiness of the youngest girl was so outstanding, so exceptional, that it couldn't be expressed or even sufficiently praised due to the shortcomings of human speech.