With all other registrars all over the world, the change was pretty easy and took about 10-60 seconds. One needed to know the addresses of their DNS servers, type them in and that was it.
But not with GoDaddy. There, the situation is very different. First of all, they do not accept server names, but IPs. Also, the IPs need to be registered first, which takes up to two days. In addition to that, the process is very unintuitive. Here's how to do it.
And that should be it.
If this still does not work, you may to try to contact the GoDaddy support, but in my case, they were not very helpful. They just sent me parts of their FAQ, which I of course had already read.