Proof of optimality:
elias has shown how to do it with 3 pieces. This is optimal.
Suppose that Bob cuts the paper into two pieces. In order to be able to put the missing square in the corners, there must be an orientation in which the cuts go down and right from the missing square, never going to the left of the vertical gray line or above the horizontal one:
The optimal case would actually be to take the whole rectangle, and I will talk as though he does, but the same applies if he loses parts of it. It's just that losing parts will add more restrictions because we won't be able to apply as many reflections and rotations and still fit in the gap in the L-shaped piece.
The rectangle must go up against two edges because it has to fit within the hole in the L-shaped piece. (If the original missing square was against the edge, the piece is no longer L-shaped, but the rectangle must then go up against three edges). If it touches the top edge then the vertical position of the gap must be against the top edge (if the left or top edge of the rectangle is placed against the top edge of the square), the rectangle's width minus one squares below it (if the right edge is placed against the top edge), or the rectangle's height minus one squares below it (if the rectangles bottom edge is placed against the top edge). If it touches the bottom edge of the square then the vertical position must be against the bottom edge, width minus one squares above it, or height minus one squares above it. That's only at most six different values, and he needs to make eight.
Alternatively,
the L shape can be rotated to put the rectangle in any of the 4 corners. The rectangle itself has at most 8 distinct orientations, so we have at most 32 distinct configurations, and we need 64.