I'm lost on how to build an arrayref-based structure from there.

You don't need to. If you create a list of keys to the original hash in your required order:

my @keysInPriorityOrder = sort { 
    $data->{Elements}{$a}->{priority} 
    <=> 
    $data->{Elements}{$b}->{priority}
} keys %{ $data->{Elements} };
[download]

Then to process the sub hashes in that order:

for my $key ( @keysInPriorityOrder ) {
    my $subhash = $data->{Elements}{ $key };
    print $subhash->{ $_ } for qw[ Priority Name OtherVal ];
}
[download]