On the first step, after clicking "Deploy" button at https://datalab.cloud.google.com/ the messages pops up
The request to deploy Cloud Datalab into project ... failed.
Please ensure that the project is enabled for billing. Additionally, you must be an owner or editor within the project.
Occasionally, a deployment request may fail due to transient errors or capacity reasons. If so, please try again.
Double checked - billing is enabled (other services work) and I'm the owner of the project.
You might not have the Google Compute Engine APIs enabled (or you didn't wait long enough after enabling them).
Follow the instructions from Getting Started page and where it says Click to: Enable the Google Compute Engine API click there and select the project to enable it on then click Enable. You'll need to wait 15+ minutes after enabling it for it to take effect.
When it's enabled correctly you should see the "Create Instance" screen at https://console.cloud.google.com/compute/instances?project=YOUR_PROJECT