The confusing "problem" is the coordinate system, it's trivial if you change it to left-down and right-down moves

               0-0
            1-0   0-1
         2-0   1-1   0-2
      3-0  *2-1   1-2   0-3
   4-0   3-1   2-2   1-3   0-4
5-0   4-1   3-2   2-3   1-4   0-5
[download]

You see in your system:

• the left coordinate is the "level", which is the sum of left-down and right-down moves
• the right coordinate is the right-down move

So your goal needs 2 left and 1 right move in any order, because this is just a distorted rectangle with 2 down and 1 right move

0-0   0-1   0-2   0-3   0-4   0-5
1-0   1-1   1-2   1-3   1-4
2-0  *2-1   2-2   2-3
3-0   3-1   3-2
4-0   4-1
5-0
[download]

This algorithm is fixing it by recalculating the remaining left-down moves

use strict;
use warnings;
use Data::Dump qw/pp dd/;


my $goal = [3,1];
my ($gl,$gr) = @$goal;

my @results;

pathfinder( [0,0,"start"] );                      # start

pp \@$_ for @results;


sub pathfinder {
    my ( $last ) = @_;

    my ( $l, $r ) = @$last ;

    if ( $gl == $l ) {
        if ($gr == $r) {
            push @results,[ reverse @_];
        } else {
            warn "wrong",pp [reverse @_];
            return
        }

    }


    # left
    pathfinder( [$l+1,$r  ,"left"], @_ ) if $l < $gl - ($gr - $r);

    # right
    pathfinder( [$l+1,$r+1,"right"], @_ ) if $r < $gr;
}
[download]

C:/Perl_64/bin\perl.exe  d:/tmp/pascale_path.pl 
[
  [0, 0, "start"],
  [1, 0, "left"],
  [2, 0, "left"],
  [3, 1, "right"],
]
[
  [0, 0, "start"],
  [1, 0, "left"],
  [2, 1, "right"],
  [3, 1, "left"],
]
[
  [0, 0, "start"],
  [1, 1, "right"],
  [2, 1, "left"],
  [3, 1, "left"],
]

Compilation finished at Thu Mar 22 12:41:53
[download]

update

in hindsight it's probably better implemented in the new coordinate system and only the results are transformed back.

The code is much easier then.