The solution provided above by sh1tn is quite general, but from the second section of your question it might be overkill. If I understand well, you actually don't need regexes at all, otherwise I wouldn't understand how you could make the test you propose as the second alternative.

Regarding the efficiency issue, I think that there shouldn't be much difference between the two approaches; I don't want to Benchmark it because I don't want to fill a directory with useless files :)

I say that because, on a very general approach, I think that the OS has to load the directory table to give to Perl, and then you end up either analysing it by yourself, or leaving Perl to do it for you, which I don't think makes much difference. If you only want to test if some file exists, I'd stick to the simpler solution, that is:

my $basedir = "/path/to/directory";
my @candidates = qw ( this and that file );
my @present = grep { -e "$basedir/$_" } @candidates;
[download]

See perldoc -f -X for variants in the test, I've put the most general "file existence" test instead of your more specific "file is a plain file", thus including directories, fifos, etc.