In case anybody gets stuck with the same problems

When baking the AO map, Blender kept baking it onto my Normal map UV image - it just switched automatically from the AO image to the NM image automatically. What helped: When both the high- and low-poly objects are selected, go into edit mode and press "A" in the viewport to select all vertices on the low-poly object. Somehow that magically fixes it.

The second one maybe I missed in the video but basically I was getting black spots where there shouldn't have been any - because I had other rocks next to my first rock. I hid the objects in the scene but it didn't help. Apparently you either have to have other objects on a different layer OR (this fixed it for me) you can disable other objects in render.