I've always just abstracted general-purpose code like this into a utility module (or modules, as makes sense). For example, I use an updated version of the module in RFC: Log::Painless to handle common logging, and subs look like this:

sub foo {
   trace enter;  #logs entry into the sub if loglevel is 'trace'
   eval {
      sub_that_might_die(shift @_);
   };
   if ($@) {
      debug caught; #logs catching of exception if loglevel is 'debug'
      warn $@;
      return;
   }
   trace leave; #logs departure from sub if loglevel is 'trace'
}
[download]

Yes, it's still repetitive to type trace enter at the top of each sub, but no more so than using attributes, and I find it's very natural. I don't know if a similar approach would address all your "cross-cutting concerns", but I thought I'd throw it out there as a possibility.

Good luck... and let us know what you decide and why, I'm curious. ;-)