Google Maps Android API: Authorization failure. Ensure that the "Google Maps Android API v2" is enabled. Ensure that the following Android Key exists

I am getting this error:

E/Google Maps Android API: Authorization failure.  Please see https://developers.google.com/maps/documentation/android-api/start for how to correctly set up the map.
E/Google Maps Android API: In the Google Developer Console (https://console.developers.google.com)
Ensure that the "Google Maps Android API v2" is enabled.
Ensure that the following Android Key exists:
    API Key: [The key...]
    Android Application (<cert_fingerprint>;<package_name>):

Instead of the map working correctly, this is what I see:

In my app/build.gradle, I have this:

implementation 'com.google.android.gms:play-services-base:16.1.0'
implementation 'com.google.android.gms:play-services-analytics:16.0.8'
implementation 'com.google.android.gms:play-services-awareness:16.0.0'
implementation 'com.google.android.gms:play-services-cast:16.2.0'
implementation 'com.google.android.gms:play-services-gcm:16.1.0'
implementation 'com.google.android.gms:play-services-location:16.0.0'

play-services-location is what I need for the Google Maps, correct? I was looking at the list at https://developers.google.com/android/guides/setup and I assume that Google Location and Activity Recognition - com.google.android.gms:play-services-location:16.0.0 is what I need for Google Maps. Is this correct?

UPDATE 1: I already have Maps SDK for Android enabled:

The error says: Ensure that the "Google Maps Android API v2" is enabled.. Is it referring to the Maps SDK for Android that I am showing in the screenshot in this UPDATE 1?

UPDATE 2: I have Maps SDK for Android enabled:

When I click the MANAGE button, I can go to the section to configure credentials that I showed in UPDATE 1.

UPDATE 3: I see the Map displayed correctly on all versions of Android on the Emulator. But on physical devices, the map never shows up. I see the Google logo and the red balloon, but now the map when I run the app on physical phones. Only on the Emulator everything works. Any ideas why?

UPDATE 4: See my solution at https://stackoverflow.com/a/56307654/4242086.

I followed this tutorial and I was able to fix it: https://www.youtube.com/watch?v=sJBlQv6IptQ. The video makes references to this tutorial: http://ramsandroid4all.blogspot.com/2016/01/google-maps-android-example-in-android.html.

In my case, what I did was to create a new project at https://console.developers.google.com/. I used Android apps for Application restrictions:

For the Restrict usage to your Android apps section, I had to provide a Package name and a SHA-1 certificate fingerprint. The Package name was in my app/build.gradle, specifically here:

applicationId "[my package name]"

The SHA-1 certificate fingerprint I found it from Android Studio by running signingReport:

The result included something like this:

Alias: AndroidDebugKey
MD5: [The value]
SHA1: [The value]
SHA-256: [The value]
Valid until: Wednesday, May 5, 2049
----------

BUILD SUCCESSFUL in 0s
1 actionable task: 1 executed
16:31:44: Task execution finished 'signingReport'.

Now the map works correctly in my Android app:

UPDATE 1: To my surprise, the maps were working correctly only on the Android Studio Emulator but not on real Android physical devices. The solution was what I posted at https://stackoverflow.com/a/56307654/4242086.