Was logged in and prompted to restart windows so it could install updates.
Clicked restart…
Went to go access VM minutes later and couldn’t make a connection. Got error: " **We couldn’t connect to the remote PC. Make sure the PC is turned on and connected to the network, and that remote access is enabled.**Error code: 0x204"
Checked Google Cloud and the instance is running and there were no changed made to the firewall, etc.
Also tried to stop and restart it from the management console with no luck at all.
You have mentioned that no changes were made on the firewall. I assume you meant the GCE firewall. If that is the case, and per this Microsoft Forum, it could be related to the internal Windows firewall, or any other security application. One way to verify, is to scan port 3389 or telnet to it as suggested in this Stackexchange comment.
To mitigate, you can make use of the instance’s metadata. For example, you may use a powershell startup script that would create a Windows firewall rule allowing traffic through port 3389 after a reboot, and as suggested in this previous thread. You may also disable it completely as suggested in this thread. On the other hand, and for further troubleshooting, you can interact with the serial port console as mentioned in this document.