It is clear that you are expecting match() to construct a variable called $bob, give it the value 45; in such a way that when the anonymous subroutine that is the third argument is run, that variable will exist and be visible to that subroutine.

What isn't clear is quite how what you are doing would achieve that goal.

A simple diagnostic run just before you invoke the anonymous sub:

use Data::Dump qw[ pp ];

...

sub match ($$$) {
    no strict 'refs';
    my ($lhs, $rhs, $fun) = @_;
    my $locals = {};
    # populate locals
    match_inner($lhs, $rhs, $locals);

    while (my ($k, $v) = each %$locals) {
        local ${$k} = $v;
    }
    pp $locals;
    return $fun->();
}
[download]

Shows that what you've done is add a key:bob with the value 45 to the hash(ref) name $locals:

C:\test>1114414.pl
Name "main::bob" used only once: possible typo at C:\test\1114414.pl l
+ine 52.
{ bob => 45 }
Use of uninitialized value $bob in print at C:\test\1114414.pl line 52
+.
[download]

What that also shows is that the first warning:Name "main::bob" used only once: is produced at compile time; ie. long before your code ever gets invoked; so nothing your code does at runtime will resolve the problem you are being warned about.

I think that's because the while loop localizes each variable only within the body of the loop.

Indeed. Everything you did with local is undone as soon as you leave the body of the loop.

In order to achieve your goal -- the declaration and initialisation of variables either within the scope of, or closed over by, your anonymous subroutine -- you would have to be modifying the symbol table prior to that anonymous subroutines compilation! Ie. You'd have to do something before your code was run.

And that a tall order unless your code is running within the compiler itself.