We set our GI/AA settings to 64, and that seemed to fill in the shadow noise nicely. We also didn't bother with the environment replacement- we just put the shadowcatcher on the floor, used a compositing tag to tell everything else not to be visible to camera (but still cast shadows), and that seemed to work fine. This requires two renders, but this way the shadows get one setting and the object itself gets another (in our case we set GI/AA to 4 for our object pass, to help with anti-aliasing and animation flickering).