Easy... ;-)

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

my @paths = find_paths
  (
   [0,0,'start'],
   [3,1,'goal']
  );

pp @paths;



sub find_paths {
    my ($start,$goal)=@_;

    # --- transform to easier coordinates
    ($start,$goal) = map old2new($_), ($start,$goal);

    # --- define closure
    my @results;
    my ($gl,$gr) = @$goal;
    my $pathfinder;

    $pathfinder = sub  {
        my ( $last ) = @_;
        # pp \@_ ;# track recursion path

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

        if ( $gl == $l and $gr == $r) {
            push @results, [ map new2old($_), reverse @_ ];
            return;
        }

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

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

    # --- init recursion
    $pathfinder->($start);

    return \@results;
}




# --------------------------------------------------
# coordinate transformations


sub old2new {                           # left = level - right
    my ($a_old)=@_;
    my @new = @$a_old;
    $new[0] = $new[0] - $new[1];
    return \@new;
}

sub new2old {                           # level = left + right
    my ($a_new)=@_;
    my @old = @$a_new;
    $old[0] = $old[0] + $old[1];
    return \@old;
}
[download]

(
  "Result:",
  [
    [
      [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"],
    ],
  ],
)
[download]

Please note, any recursion can be written as iteration. If speed matters this might be worth it.

tybalt is using the same algorithm, just starting from the end (so he doesn't need to reverse the path) and more golfy.