Part of your problem here, is that you have more information than you're giving the computer. i.e. they're not just regex but file system path expressions.
You might take advantage of that knowledge and decompose the regex into a set of File::Find::Rule rules,
obviously you'll have to write the parser youself, but hopefully all the regexes will be quite similar and there will be common patterns that you can spot and translate into rules.
So you might end up with something like :-
my @dirs = File::Find::Rule->directory()->name(qr/blah[0-9]/)->in('
my @files = File::Find::Rule->file()->name('setup.exe')->in(@dirs);
It's an interesting problem and well worth spending some time on.