One method is to use recursion in combination with dispatch tables:

use strict;
use warnings;

my %dispatch = 
  (
   # scalar
   ''        => sub { my ( $element, $op ) = @_;
              $op->( $element );
            },
   'HASH'    => sub { my ( $element, $op ) = @_;
              for my $key (keys %{$element}) {
            search_and_replace_in_hash( $element->{$key}, $op );
              }
            },
   'ARRAY'   => sub { my ( $element, $op ) = @_;
              search_and_replace_in_hash( $_, $op) for @{$element};
            },
   'default' => sub { my ( $element, $op ) = @_;
              print STDERR ref($element).": unknown type of reference\
+n" 
            },
  );

# operates on references
sub search_and_replace_in_hash {
  &{ $dispatch{ ref($_[0]) } // $dispatch{'default'} }(@_);
}

my $var = { "0x55555555" => { "0x55555555" => [ ["0xAAAAAAAA", "0x9"],
+ ],
                  "0xAAAAAAAA" => [ ["0xAAAAAAAA", "0x8"], ],  },
        "0xAAAAAAAA" => { "0x55555555" => [ ["0xFFFFFFFF", "0x8"], ],
                  "0xAAAAAAAA" => [ ["0x55555554", "0x3"], ],  },  };

search_and_replace_in_hash( $var, sub { $_ =~ s/0x//; } );
search_and_replace_in_hash( $var, sub { print "$_\n"; } ); # no need f
+or Data::Dumper
[download]

For other types of references, you need to expand the dispatch table accordingly.

Thanks to Rolf for his helpful comments above.