This is an adaptation on an idea presented the Perl Cookbook (O'Reilly). Don't count on @diff being in any particular order though.

use strict;
use warnings;
my @AOA1 = ( [2342, 1], [2444, 2], [3333, 3] );
my @AOA2 = ( [2444, 2], [3333, 3], [1234, 1] );
my @diff;
{
    my %crossref;
    $crossref{ join "|", @{$_} }++ foreach ( @AOA1, @AOA2 );
    foreach my $key ( keys %crossref ) {
        push @diff, [ split( /\|/, $key ) ] if $crossref{$key} < 2;
    }
}
print "@{$_}\n" for @diff;
[download]

This assumes that "Difference" is defined as elements that are only found in one of the two arrays.

Update: Fixed a typo in the split call.