Bootcamp: The startup disk does not have enough space to be partitioned
Okay, the solution is that I did not disable Time Machine and remove all backup drives first. Doing that solved the issue. So the full solution is:

Disable "Backup Up Automatically" in Time Machine System Preferences, and remove all backup drives, such that it looks like this:



Then run sudo tmutil thinlocalsnapshots / 999999999999

And try again. Optionally restart the computer and try again.