Which formal language class are XML and JSON with unique keys?
Using BNF with your unique-repetition operator, x := S^ says that an x is an instance a of symbol S, optionally followed by an instance b of set S - a, itself optionally followed by an instance c of set S - a - b, and so forth. If |S| is the number of possible S, and is finite, then 2 ^ |S|! - 1 is the number of possible S^.

It's not really meaningful to talk in terms of the computational power of the language being described, since this is about static semantics, in the twilight between syntax and ordinary (dynamic) semantics. The expressive power of the grammar is extended, since it has a formal means of expressing a particular type of input adaptation.

Specifically, it provides a means of accepting a permutation of a subset of a particular set. I don't think there is any existing name for this class of language. It's certainly not context-free, but the context requirement is at least pretty strictly controlled. If you need a term for it, just coin one. I suggest context-respecting for the class of languages that cannot be described by a context-free grammar without additional embedded information about static semantic constraints, which to be fair are vaguely syntactic in spirit.

The most useful application of this particular extension is probably just the ability to introduce unique-key constraints, but it also lets you describe such interesting sets as x := [0-7]^, which matches any octal number of 8 or fewer non-repeated digits. As for the complexity of it, determining whether an element of the set has been seen is no worse than logarithmic, and the frequency of checking is linear in the number of elements matched, so the ^ operator is indeed decidable in worst-case linearithmic time.