We encountered a similar problem in our operational environments today. We successfully completed the terraform 0.13upgrade command. This indeed introduced a versions.tf file.
However, performing a terraform init with this setup was still not possible, and the following error popped up:
Error: Invalid legacy provider address
Further investigation in the state file revealed that, for some resources, the provider block was not updated. We hence had to run the following command to finalize the upgrade process.
terraform state replace-provider "registry.terraform.io/-/google" "hashicorp/google"
EDIT Deployment to the next environment revealed that this was caused by conditional resources. To easily enable/disable some resources we leverage the count attribute and use either 0 or 1. For the resources with count = 0, that were unaltered with Terraform 0.13, the provider was not updated.