My inclination was to use a second capture, and then decrement the position. What is the performance penalty for changing the search position? More than just saving an index value?

#! /usr/bin/perl -w

use strict;
use warnings;

my $a = "Input String: aaAabBAAa";

my $n = shift @ARGV;
$n --;

while ( $a =~ /((.)\2{$n})/ig )
{
    print "$1\n";
    pos($a) -= $n;
}
[download]

Of course, this doesn't really answer the elegance question, darn it.