I would first start with the observation that keys are strings - not objects. And qr creates an object. Which happens to stringify into something that can recreate the object. It's DWIMmery, for sure, but ... not quite deterministic.

What this looks like to me is actually an AoH:

my @dispatch_table = (
  {
    re => qr/^(?!START:|END:)([^*: ][^:]+):(.+)\n/,
    action => \&header,
  },
  {
    re => qr/^START:\s*(.+)\n/,
    action => sub { $_[0]->{starttime} = $_[1] },
  },
  {
    re => qr/^END:\s*(.+)\n/,
    action => sub { $_[0]->{endtime}   = $_[1] },
  },
  {
    re => qr/^(?:\* |  )([^:]+):(\d+):(.+)\n/,
    action => sub { push @{shift->{items}}, \@_ },
  },
);
[download]

What this does is put your re and action close together, it also puts the order of execution completely in your control (right now you're relying on keys to give you the order, which may be unrelated to the order you insert them), and you can also put other fields in there for further actions, data, whatever, that you may need to. For example, two re's may go to the same code ref, but you could pass extra args that were different for each, and these extra args could be here.

foreach my $h (@dispatch_table) {
  if (my @m = $line =~ $h->{re}) {
    $h->{action}->($r, @m);
    # or $h->{action}->($r, @m, $h->{args});
    next LINE;
  }
}
[download]

IMO, that's cleaner and more flexible. YMMV.