I may have found a solution that worked for me
Head to https://console.cloud.google.com/ select the correct project, from the navigation menu select APIs & Services and head onto the OAuth consent screen
If the publishing status is like in the image, click on BACK TO TESTING
After that, try to add the device again in the Google Home app and it should appear