MacBook Pro not Connecting to iOS 13 Personal Hotspot

I just installed iOS 13 on my iPhone XS Max and found that my two MacBook Pros (2017, 10.14.6) cannot connect to the iPhone's personal wifi hotspot anymore. To be more accurate: at first, the MacBooks connect, but after less than 5 seconds, the connection gets lost. USB tethering still works though.

Am not seeing this issue on my iPad (wifi, 2018): it still connects seamlessly to the iPhone's wifi hotspot. In fact, as along as the iPad is connected, even the MacBooks stay connected. However, disconnecting the iPad will also drop the MacBooks' connection immediately.

Also, the MacBooks connect successfully when I remove (lock out from) the iCloud account in macOS.

All devices are linked to the same iCloud account. Of course, I already tried restarting my devices :-)

Other, non-Apple devices can also connect without any problems