You are forgetting about the aqueous environment the protein is folding in. Typically proteins fold in such a way that hydrophobic sections of the protein are hidden from the aqueous environment and hydrophilic sections are not. This means that even though the entropy decreases in just the confirmation of the protein, the entropy of the aqueous environment increases much more. The environment has many more accessible orientations when the hydrophobic sections are hidden and the hydrophilic sections are exposed, and thus entropy overall still increases.

A recent [SciShow video](https://youtu.be/a_BKQ_ZPImw) covers this exact idea.