I'm considering something like ...

So what happened when you tried it?

c:\@Work\Perl\monks>perl -wMstrict -MData::Dump -le
"my %h = qw(foo oofzle  bar rabzle  quux xuuqzle  fee eefzle);
 dd \%h;
 ;;
 my @k = grep m{ foo | bar }xms, keys %h;
 ;;
 map s/zle/DING/, @h{ @k };
 dd \%h;
"
{ bar => "rabzle", fee => "eefzle", foo => "oofzle", quux => "xuuqzle"
+ }

{ bar => "rabDING", fee => "eefzle", foo => "oofDING", quux => "xuuqzl
+e" }
[download]

Although I have to say I don't understand your general for-aversion — and map contains an implicit loop!

Update: Small change to example code to make it closer to structure of OPed pseudo-code.