The problem is that an entry might change from a directory to a symbolic link between the stat() and the open().

Wouldn't a second stat() after the open tell? Well duh, the underlying file could just switch back from symlink to directory between the open() and the second stat, e.g. something that emulates a directory via a maliciously loaded file system module doing sinister things. Just curious - what problem are you trying to solve?

Correct me if I am wrong, but after getting a handle to something, even if the something is renamed, deleted, and symlinked back, it holds to the original structure being accessed:

my $path = '/tmp/open';
-d $path and die "remove $path first\n";
mkdir $path;
for (qw(foo bar quux)) {
    open my $fh, '>',"$path/$_";
}
mkdir "$path/baz";
for (qw(blorf blorfldyick)) {
    open my $fh,'>', "$path/baz/$_";
}
opendir my $dh1, $path;
while(readdir $dh1) {
    next if /^\.\.?$/;
    print "read(dh1): $path/$_\n";
    if (-d "$path/$_") {
        opendir my $dh2, "$path/$_" or die;
        # emulate external change directory to symlink
        rename "$path/$_","$path/fie";
        symlink "$path/fie", "$path/$_" or die;
        # end emulate
        if(-l "$path/$_") { 
            print "bogus change to $path/$_:\n";
            print "  $path/$_ points to ",readlink "$path/$_","\n";
        }
        while (my $e = readdir $dh2) {
            next if $e =~ /^\.\.?$/;
            print "read(dh2): $e\n";
        }
    }
}
__END__
read(dh1): /tmp/open/foo
read(dh1): /tmp/open/quux
read(dh1): /tmp/open/baz
bogus change to /tmp/open/baz:
  /tmp/open/baz points to /tmp/open/fie
read(dh2): blorf
read(dh2): blorfldyick
read(dh1): /tmp/open/bar
[download]

Side note which might resolve this XY Problem (if so): -d on a symlink returns true up to v5.25.10, so -d resolves symlinks, which it shouldn't do. IMHO this is a bug.

Apropos race condition: I can't think of anything which would resolve that, other than a system call like openif() into which the expected type is passed as an argument.