I faced the same situation a year ago. I had enough free storage shown in Finder, but I couldn't use it. For me, it was because because it was "purgeable".
You can check this in Apple Disk Utility --> Go to the drive --> Check the stats "Available" and "Purgeable".
If te Purgeable number is large (Gigabytes), you have to check this:
https://apple.stackexchange.com/questions/254676/how-do-i-clear-the-purgeable-area-on-my-disk
It's not the first (accepted) solution that solved it for me, but the second one: "You can create a huge file that will force macOS to clean purgeable files to free you space. Do do so...".
The faster way is to create a huge file using Disk utility, then delete that file. To create that file:
- Launch Disk Utility and choose “New Image”
- Name the file as appropriate, then pull down the “Size” sub menu and select a file size appropriate for your needs
- Ignore all other settings and choose “Create”
After the huge file (make it almost as large as the purgeable size) was created, delete it, and all available space was truly available. Let me know if this solved your problem too!
If this is not the case for you, it could be because the App Store download actually requires twice the App download size as disk space. For Xcode this is pretty huge, but your 39 GB should be more than enough. Nevertheless I always prefer installing Xcode manually (normally listed here), by simply downloading the file and extracting it. It gives me more freedom over Xcode versions. The only problem with this, is that Apple still hasn't listed the full Xcode 13 download on that page, even now a full day after public release. So I'm still waiting...
