Habe ich zwar, wurde aber alles probehalber deaktiviert.
Mittlerweile hat sich das Problem aber erledigt.
Folgendes:
Habe nochmals (zum x-ten Mal) alle Google Cookies gelöscht.
Bin dann auf die englische (co.uk) Googel Einstellungsseite gegangen. Habe dort keine Cookiewarnung bekommen. Habe dort aber auch nichts eingestellt.
Daraufhin auf die deutsche Einstellungsseite gegangen. Dort auch keine Warnung mehr bekommen. Einstellungen durchgeführt.
Alles OK.
Jetzt frag mich bitte nicht wie das sein kann. Ich verstehe es auch nicht.
Habe nichts irgendwie anders gemacht als sonst auch schon, außer bei google.co.uk versucht.