Found the answer: The problem seems to be an old version of paket.
First thing to try: delete paket.exe and Paket.Restore from the folder .paket, then execute paket.bootstrapper.exe.
For me this didn't work, so I downloaded the latest version of paket.bootstrapper.exe manually and executed that. The file is called paket.exe in the official repository, so you have to rename it to paket.bootstrapper.exe.
https://github.com/fsprojects/Paket/blob/master/.paket