That fails when $n == 0 and when $n == 1. One way to fix it is to apply both of the following changes:

Change
while --$n
to
while $n--

Change
my $n = int rand $nKeys;
to
my $n = 1 + int rand $nKeys;

Update: Might as well post the modified code:

sub getRandomPairFromHash{
    my $href = shift;
    my $nKeys = keys %$href
       or return ( undef, undef );
    my $n = 1 + int rand $nKeys;
    my( $key, $val );
    ( $key, $val ) = each %$href while $n--;
    return ( $key, $val )
}
[download]