Here's some quick thoughts off the top...

Rescale your coordinates by 4 so that 8.5 x 11 becomes 34 x 44, and your rectangles of 2.75 x 3 become 11 x 12.

Now you can draw the line vertically anywhere from 0 to 34, and call the horizontal function with the 2 pieces. The horizontal function then chooses, on each piece, anywhere between 1 and 44, and calls the vertical function on the 2 pieces. [No need to use 0 instead of 1, because it's time to make a cut!]

You need to work out how to represent these, and how to avoid infinite recursion.

Perhaps like this:

sub vert
{
    my @{@piece[0]} = @_[0,1];
    my @{@piece[1]} = @_[2,3];
    my $depth       = @_[4] + 1;

    for my $piece ( 0..1 )
    {
        for my $x ( 0 .. $piece[$piece][0] )
        {
            next unless ( $x or ( $depth > 1 ));
            horz( $x,                     $piece[$piece][1], 
                  $piece[$piece][0] - $x, $piece[$piece][1],
                  $depth );
        }
    }
} # sub vert

sub horz
{
    # similar code for horz
}

my ($scrap, $count1, $count2) = vert( 34, 44, 0, 0, 0 );
[download]

Now, you'll have to work out when to stop recursing, like when it gets smaller than your target rectangle, or when you have enough of both rectangles. And vert and horz should count up how what the minimum scrap is at each recursion level, and pass that back, along with how many of each rectangle are available, etc.

There's really quite a bit more work to do here, and some of it is rather subtle. Maybe this will get you started, so you can ask the bigger questions.

-QM
--
Quantum Mechanics: The dreams stuff is made of