It's not hard to modify it so that the location of the use statement doesn't matter:

package Signatures;

my @packages;

sub import {
    my $package = caller;
    push @packages, $package;
}

INIT {
    for my $package (@packages) {
        no warnings;
        no strict;
        for (keys %{ $package . '::' }) {
            next unless exists &{ $package . "::$_" };
            my $sub = \&{ $package . "::$_" };
            next unless my $proto = prototype $sub;
            eval qq {
                package $package;
                sub $_ {
                    local ($proto) = \@_;
                    \$sub->()
                }
            }
        }
    }
}

1;
[download]

It still seems like the function using the prototype has to be defined AFTER any calls to it though. And modules using the Signatures have to be used after all calls to the functions in them. Otherwise I get "Malformed prototype for foo: $a,$b at C:\temp\Proto\test.pl line 6." Not sure if there is any way around that. And I don't see any way to lexicalize the parameters and make strict happy.