As mentioned in the comments, this problem is known to be NP-hard. So, the only fast algorithms you're going to get will be approximation algorithms or heuristic. As this is a common practical problem (packaging for logistics, for example), there are many heuristic algorithms, both general and with more assumptions.
A lot approaches ignore rotation, but can be expanded fairly easily to support it. As you seem to be aware of approaches without rotation, I'll focus on the rotating part.
A good resource is 'One thousand ways to pack the bin', by Jukka Jylänki. It covers many heuristic algorithms, and considers rotation part of the problem. Most of the rest of this post summarizes this paper.
While rotation makes the problem a lot harder to solve exactly, it doesn't make most heuristic methods much more complicated, as they cannot afford to make complicated choices and so choose heuristically how to rotate.
For the shelf algorithms, rotation is quite simple:
- If the current rectangle starts a new shelf, we rotate such that the shelf height is minimal.
- Otherwise, rotate such that the width is minimal while still fitting the shelf (if it fits at all)
Point 2 is actually the best way to rotate given that the rectangle will be packed in the current shelf while for point 1 one could argue to do the opposite and this could indeed be better in some cases. (such as the case that all remaining rectangles are squares with length equal to the long side of the first rectangle of the shelf)
For the guillotine algorithm, the choice for rotation isn't so clear (perhaps a reason why Jylänki leaves this open), but one reasonable method is to try both orientations to decide whether a rectangle 'fits'. If both fit, one could try to pick the one that matches the split rule (for example, choose the rotation that minimizes the area of the chosen free rectangle when using the Best Area Fit variant)
For the Maximal rectangle algorithm and the Skyline heuristic, supporting rotation here is similar to the Guillotine case, there aren't really any particular choices other than trying to fit with both orientations and pick the one which makes more 'sense' with respect to the rest of the specific heuristic.
There are more algorithms, but I think this gives a good overview of the ideas of how to support rotation. As you might have noticed, these methods aren't too fancy, that is sometimes the best you're going to get.