That makes sense, since Maker is the package in which it was compiled

So compile it in the right package:

package Maker;

sub make {
    my $pkg = caller;

    my $sub = eval <<"    __EOI__" or die $@;
        package $pkg;

        sub {
            my \$self = shift;
            print "w00t\\n";
            \$self->SUPER::go;
        }
    __EOI__

    no strict 'refs';
    *{ $pkg . '::go' } = $sub;
}
[download]

Update: or easier (since only doubled slashes need to be escaped):

package Maker;

sub make {
    my $pkg = caller;

    my $sub_body = <<'    __EOI__';
        sub {
            my $self = shift;
            print "w00t\n";
            $self->SUPER::go;
        }
    __EOI__

    my $sub = eval "package $pkg; $sub_body" or die $@;

    no strict 'refs';
    *{ $pkg . '::go' } = $sub;
}
[download]

Update: Oops, just noted your comment about eval. The only alternative is to play with the ref($self)'s @ISA, which is what the aformentioned SUPER module does.