Thanks David, that helped.
Apparently adding the location of libsodium.a to the Path does not actually work. However, adding SODIUM_LIB_DIR as a new environment variable with the location of libsodium.a as its value did the trick. Everything compiled after that, but the tests failed. The solution was moving libsodium-win64\bin\libsodium-13.dll to C:\Windows\System32 and all tests passed after that.