I don't think anyone's suggested this yet:

$_ = <INFO> until !defined($_) || /^(\* Menu:|\037)/;
return %header unless /Menu/;
[download]

Although that spits out warnings under -w, so maybe:

$_ = <INFO> until !defined($_) || /^(\* Menu:|\037)/;
return %header unless defined and /Menu/;
[download]

and you don't really need the second regex so maybe:

$_ = <INFO> until !defined($_) || /^(\* Menu:|\037)/;
return %header unless defined and index($_, 'Menu') >= 0;
[download]

Or if you want to split the regex:

my $menu;
$_ = <INFO> until !defined($_) || ($menu = /^\* Menu:/) || /^\037/;
return %header unless $menu;
[download]

And then of course you could use substr() instead of a regex for the \037 test...

Oops just realized that the 1st, 2nd, and 3rd solutions presuppose that you don't have 'Menu' AFTER the \037 (which could be fixed with a '^ *' in the 1st & 2nd answers)...