That's always an interesting question when it comes to non-typed languages. There are a couple things I try to keep in mind when commenting on the method signature of most things I'm working on:

1.) Return more than one value
In my opinion, data structures are like objects in that they need to have a generic, singular purpose. I try to avoid having to explain why a hash-ref or an AoH has data on three different and otherwise exclusive things just to maintain a single reference in code. That's just as confusing as anything. In your example, you have an array returning hash-refs that are completely different from one another. I can't, for example, take the list and iterate over it expecting a single DDL. I would either have to test for a key, or shift off the stack and hope things are in the right order. There is no real good way to document something like this.

A recommendation on this would be to simply break up the AoH into singular hashes. For each, either return a defined structure from a sinle method (ie return $href_original, $href_changes .... Or, have many methods that return the respective piece of data. This way, you can not only comment on what is happening, but the code is a bit more self-documenting as well.
Such as:

#
# Intended to be the caller
#
my $originals = $self->get_originals();
my $changes   = $self->get_changes();

#
# Intended to be the 'offending' package
#
 ... 
sub get_originals {
  return $_[0]->{'original'};
}

sub get_changes {
  return $_[0]->{'changes'}
}
[download]

2.) Don't be afraid to comment with structures and text
The point being, really, that commenting with a pseudo-structure is sometimes the best way to describe what something should look at. Furthermore, comments aren't ususally pointed at yourself (at least I tend to remember code I've written, for the most part). That said, if a cohort doesn't understand the look of a complex data structure either a) They shouldn't be programming Perl b) They will ask someone anyways (me or otherwise). Furthermore, adding text around the structure to explain what they keys *are*, not just their data-type is always useful.

This could really go on and on, and I'm sure by the time I've posted this there is already three other good examples. The point I am really trying to make is: make sure your structures make sense in the first place *then* don't be afraid to use pseudo-code as a descriptive characteristic in the comments of a method signature.