2 answers
Check if the default access to Case object is set to "Private"
Setup -> Sharing Settings -> Organization-Wide Defaults -> Click "Edit"
The hint is the body of the trail: "If you remember, in an earlier step we set the external org-wide default on cases to private." (no, we did not).
Now case object is available in the "New Sharing Set"