Following up on what roubi(++) said, if you still want to do it your way, you need to maintain the aliasing of $_[0]. This code does what you expect:

sub Add_key_and_value {
  our $ref;    # so that "Strict" does not complain (use vars qw[$ref]
+ also works)
  local *ref = \$_[0];  # when "$ref" springs into existence, aliased 
+to $_[0]
  my (undef, $key, $value ) = @_;

  $ref->{ $key } = $value;
}
[download]