I had the same problem with the Wyze Plug Outdoor appearing to fail to connect to the wifi. What finally worked was trying to set it up through a different device (a 2018 iPad), whereupon the setup completed successfully. I even tried multiple times to make sure it wasn’t a fluke, and it worked flawlessly.
Before this, I had tried connecting through two different Android phones (2013 & 2017 vintage), returned my original plug for another, disabled this and that on the phones, messed with my router, all sorts of things. Eventually it dawned on me that even though the setup screen seemed to be indicating that the plug was attempting to connect to the wifi, in reality it was still in the process of trying to connect to my device through Bluetooth (which is why that screen says to keep your phone nearby). As it seemed to be some sort of Bluetooth compatibility issue, I tried the third device (the most modern one I have) and it worked like a charm.
So my suggestion would be to try to set up the plug through as many of the devices you have access to, and hopefully one of them is compatible. Perhaps it’s a matter of supporting the Bluetooth 5 specification (IIRC it came out early 2017, so my 2017 phone probably doesn’t have it, while the 2018 iPad does). It could also be an iOS vs Android issue. I can only speculate.