That was the error description I got: "When starting the network does not work. I have to do a lot of things to make it work." Later I got more infos: "It says there are 7 errors. If I let it fix it it has to restart and then works".
It turns out that these 7 errors are all SE-Linux-Errors. Something about /etc/resolv.conf not being readable. The error helper suggests to fix it for now and also some command to fix it permanently, those commands fail and do nothing. So of course I just deactivated that SE-bullshit.
Really, fucking vanilla Fedora on a mainstream Gnome3 desktop. What the hell are they thinking?