A hash slice and delete will do this handily,

@{$href}{map {to_new($_)} keys %$href}  # wrong
    = delete @{$href}{keys %$href};
[download]

Since the values are all scalar hashrefs, this code doesn't care about their contents, and leaves them alone.

Update: Roger++ points out that the keys got clobbered. Mapping the new keys externally fixes that,

my @newkeys = map {to_new($_)} keys %$href;
@{$href}{@newkeys} = delete @{$href}{keys %$href};
[download]