It is most likely a perfect aspect marker.
First, perfect tense using to be as the auxiliary verb sounds archaic in modern English, but Tolkien, as a scholar of early literature, would have known that early modern English still formed the perfect tense using to be with some intransitive verbs like to flee. The public OED blog explains:
The perfect of intransitive verbs, especially verbs of motion, continued (as in Middle English) to be frequently formed with to be rather than to have. Shakespeare normally uses to be with creep, enter, flee, go, meet, retire, ride, and run.
This usage appears in the final stanza of The Angel by William Blake:
Soon my Angel came again;
I was armed, he came in vain;
For the time of youth was fled,
And grey hairs were on my head.
Here is the tense/aspect broken down:
the time of youth fled (simple past)
the time of youth has fled (present perfect)
the time of youth is fled (archaic present perfect)
the time of youth had fled (past perfect)
the time of youth was fled (archaic past perfect)
The perfect aspect combined with the past tense signals that the time fled some time ago. Similarly, Luthien had fled.
The other interpretation (fled as a past participle serving as an adjective complement to Luthien) is possible, but unnecessary; Tolkien uses perfect aspect with to be in situations where the main verb wouldn't be mistaken for a participle. For example:
... all that fled his onset fled in amaze, thinking that Orome himself was come (Silmarillion)
Come in this form fits the same archaic form - an intransitive verb of movement - as shown in the King James Bible, Mark 15:42:
And now when the even was come, because it was the preparation, that is, the day before the sabbath,
Modern speakers would use had come, as the English Standard Version of the same verse shows:
And when evening had come, since it was the day of Preparation, that is, the day before the Sabbath,
So, similarly, if Tolkien had written in a more modern register, he might have written:
Orome himself had come.
and
Luthien had fled.