Here is a recursive solution. It uses the diagonal sorted in descending order but keeps track of the original order. It stops if the remaining elements become too small. I have to admit that I only looked at your one test case and that I did not do any benchmarking.

use strict;
use warnings;
use List::Util qw/ sum min /;

sub find {
    my( $array, $n, $k, $threshold, $start, $solution, $result ) = @_;
    return if sum( @{$array}[$start..min($start+$k-1,$n-1)] ) <= $thre
+shold; # not enough meat anymore
    if( 1==$k ) {
        push @$result, [ @$solution, $array->[$_][1] ] for grep { $arr
+ay->[$_][0] > $threshold } $start..$n-1;
    } else {
        find( $array, $n, $k-1, $threshold-$array->[$_][0], $_+1, [ @$
+solution, $array->[$_][1] ], $result ) for $start..$n-$k;
    }
}

my $MTX = [
       [4,-1,-2,-2, 0,-1],
       [-1,5, 0, 2,-3, 1],
       [-2,0, 6, 1,-3, 5],
       [-2,2, 1, 7,-3, 0],
       [0,-3,-3,-3, 8,-3],
       [-1,1, 5, 0,-3, 9],
      ];

my $k = 3;
my $threshold = 17;

my $n = @$MTX;
my @diag = sort {$b->[0]<=>$a->[0]} map { [$MTX->[$_][$_],$_] } 0..$n-
+1;
my @result;
find( \@diag, $n, $k, $threshold, 0, [], \@result );

print "@$_: ".sum(map{$MTX->[$_][$_]}@$_)."\n" for @result;
[download]

Update: Minor improvement. The line

can be replaced with

to avoid a few tests.