Why am I unable to push docker image in gce (gcr.io)?
From the Before you begin section of the instructions you referenced:


  Make sure that you:
  
  
  Have access to the registries which you will be pushing to and pulling from
  


This is specified in more details in Using Container Registry with Google Cloud Platform:


  To push private Docker images from a Compute Engine instance, your
  instance must have read-write or full-control permission to
  the image's bucket.


So the GCS bucket corresponding to gcr.io (or whichever GCR domain you want to use) and the desired cloud project must already be created and your GCE instance's service account must have the necessary role/permissions for push operations.

It's true, the instructions you referenced mention in Push the tagged image to Container Registry:


  When you push an image to a registry with a new hostname, Container
  Registry creates a storage bucket in the specified multi-regional
  location.


So I believe you'd have to:


first create create the bucket by executing a push to the desired GCR domain and project, but: 


from your own computer (or some machine which is not a GCE instance, but YMMV)
using the credentials of an acceptable identity, not the GCE instance service account's ones. I'd try with a real user credentials, I'm not sure if a service account's ones would cut it.

after the bucket is created add to its access control the GCE instance service account's role/permissions for push operations
then perform pushes from the GCE instance