Check whether a list of list of string fits a regex efficiently
Bonus points if someone can calculate the asymptotic time my algorithm takes.

Too much. It's exponential, as you're generating the whole candidate set. Even the improvement by rolfl doesn't change it.
You could do much better by analyzing the regex. For example &quot;\\d{3}&quot; will never match anything starting with a letter and you could cut off many possibilities. However, doing this in general is pretty complicated.
There's a method which might do this for you: hitEnd. I'm not sure if it does the right thing, but I guess so:

Returns true if the end of input was hit by the search engine in the last match operation performed by this matcher.
When this method returns true, then it is possible that more input would have changed the result of the last search.

So you could test you incomplete candidates against the regex and possibly save yourself the work with expanding them.