BTW. Always, the easiest, safest way to approach threading complex applications, is to write a single-threaded version that operates upon the data in a serial fashion.

Once you have that working, if the data is truly independent, parallelising it is usually quite simple.

For completeness, here is another example based on yours that uses a pool of threads. It is hardly more complicated than the first version:

#! perl -slw
use strict;
use threads;
use threads::shared;
use Thread::Queue;
use Data::Dump qw[ pp ];

sub helper {
    my $Q = shift;
    while( my $ref = $Q->dequeue ) {;
        lock $ref;
        $ref->{NEW_KEY} = 1;
    }
}

sub my_sub {
    my( $ref, $n ) = @_;
    my $Q = new Thread::Queue;
    my @threads = map async( \&helper, $Q ), 1 .. $n;
    $Q->enqueue( values %{ $ref } );
    $Q->enqueue( (undef) x $n );
    $_->join for @threads;
}

my $hoh = {
    A => shared_clone( { NAME => 'aa' } ),
    B => shared_clone( { NAME => 'bb' } ),
};

pp $hoh;
my_sub( $hoh, 2 );
pp $hoh;
[download]

The output is identical to the earlier version.