So...kurz vor der kompletten Verzweiflung habe ich noch diesen Beitrag gefunden:
https://www.shelly-support.eu/lexikon/index.php?entry/42-probleme-einbindung-ins-wlan-heimnetzwerk/
Hierbei ist erwähnt, dass auch geprüft werden soll, dass neue WLAN-Geräte zugelassen werden sollen. Dies hat mich dazu veranlasst nochmals alle Einstellungen des Routers zu prüfen. Es gab zwar keine Einschränkungen bezüglich dem Zulassen von neuen Geräten (dies war alles sichergestellt). Allerdings habe ich dabei festgestellt, dass das WLAN-Passwort nur für das 5Ghz-Netz gesetzt war und für das 2.4Ghz nicht. Also dort ein neues PW gesetzt und die SSID mal auf KellerLan24 geändert....siehe da, nun klappt die Verbindung im ersten Versuch. Weshalb ich mit dem 5Ghz-Passwort bislang auf das 2.4Ghz-Netz zugreifen konnte (klappte ja mit Handy und Laptop) ist mir zwar ein absolutes Rätsel, aber nun gut.
Vielen Dank für Eure Hilfe!