Here's one approach

package deprecated;

use Carp qw/ carp croak /;
use vars '%subs';
sub import {
  my($good_self, @subs) = @_;
  my $pkg               = caller;

  *{"$pkg\::AUTOLOAD"} = sub {
    croak "unknown subroutine '$AUTOLOAD'"
      unless exists $deprecated::subs{$AUTOLOAD};

    carp "deprecated subroutine '$AUTOLOAD'";
    *$AUTOLOAD = $deprecated::subs{$AUTOLOAD};
    goto &$AUTOLOAD;
  } unless defined &{"$pkg\::AUTOLOAD"};

  for(@subs) {
    $subs{"$pkg\::$_"} = \&{"$pkg\::$_"};
    *{"$pkg\::$_"}     = *{"dummy_$pkg\_$_"};
  }
}

q[ the end is nigh ... ];
[download]

And some example usage

{
  package foo;

  sub func1 { print "old\n" }
  sub func2 { print "older\n" }
  sub func3 { print "new\n" }

  use deprecated qw/ func1 func2 /;
}

print "calling: func1\n";
foo->func1;
print "calling: func2\n";
foo->func2;
print "calling: func3\n";
foo->func3;

print "calling: func1 again ...\n";
foo->func1;

__output__

calling: func1
deprecated subroutine 'foo::func1' at deprecated_test.pl line 13
old
calling: func2
deprecated subroutine 'foo::func2' at deprecated_test.pl line 15
older
calling: func3
new
calling: func1 again ...
old
[download]

Note that use deprecated goes after the subroutine declarations, so they're populated when it goes to insert the dummy routines.

Briefly, what it does is create an AUTOLOAD method that will carp and then replace the dummy subroutine with the actual subroutine.