As I mentioned under another comment, I got an Apple Watch 5 Ceramic Edition and tried to pair it with my iPhone 13 Pro, which is on iOS 15.1.1, so it's the newest Update possible at the moment. I tried every "Solution" in this whole forum, sadly nothing worked for me. I called up the Apple Support and we went trough some troubleshooting, without success. At the end he basically said that I need to send in my Watch and get it replaced for around 900€, that's actually more than i paid for it lol. I made an appointment at the Genius Bar for Monday, I will update my Comment here then.