You just need to be a bit cleverer about the keys in your %seen hash.

#!/usr/bin/perl

use strict;
use warnings;

use Data::Dumper;

my @AoA=(["1","15"], ["2","5"], ["3","4"], ["3","5"], ["3","8"],
         ["3","5"], ["4","6"], ["4","5"]);

my %seen;
@AoA = grep { ! $seen{join $;, @$_}++ } @AoA;

print Dumper \@AoA;
[download]