package redefine;

use warnings;
use strict;

my @redefines = qw( module::function foo::bar );

sub import {
    my $class = shift;
    my $caller = caller;

    no strict 'refs';
    no warnings qw/redefine/;

    for my $sym (@redefines) {
         "unqualify" subs
        (my $sub = $sym) =~ s/.*:://;
        if ( ${$caller.'::'}{$sub} &&
             *{$caller.'::'.$sub}{CODE} eq *$sym{CODE} ) {

            *{$caller.'::'.$sub} = \&$sub;
        }
        *{$sym} = \&$sub;
    }
}   

sub function {
    package module;
    print "new\n";
};  

sub bar {
    package foo;
    print "in bar\n";
}   
1;
[download]

No need to 'use module' in your redefining package (if you 'use redefine' after 'use module', that is). Adding a package declaration to the new functions gives them access to that packages' symbol table (for 'our' vars, other functions etc.)

update: made code more "general-purpose"

update 2: added package declarations to subs

_($_=" "x(1<<5)."?\n".q·/)Oo.  G°\        /
                              /\_¯/(q    /
----------------------------  \__(m.====·.(_("always off the crowd"))."·
");sub _{s./.($e="'Itrs `mnsgdq Gdbj O`qkdq")=~y/"-y/#-z/;$e.e && print}