Perhaps a bit simpler with values since the second-level hashes you are getting the keys of are the values of the first-level hash. However, if order is important you will have to sort keys in some fashion.

johngg@abouriou:~/perl/Monks$ perl -Mstrict -Mwarnings -E '
my %replaces = (
   foo => { W100 => q{W102}, W101 => q{W103} },
   bar => { W120 => q{W99},  W121 => q{W104} },
   );

my $expr = join q{|}, map { keys %{ $_ } } values %replaces;
say $expr;'
W121|W120|W101|W100
[download]

I hope this is helpful.