I was having the same problem as Madoke, and I may have figured it out, not too sure, so someone with the same problem may have to try it.
1. Go to Google API Console
2. Go to your API Project
https://gyazo.com/52c65b1179b2625e988e2185b1678b423. In the IAM & admin panel chose Crytographic Keys from the left menu
https://gyazo.com/ae68f5b47bf9c8aed93a8bc2143fb32f4. Notice it gives you a warning about the change in an area to go to that handles Cloud Key Management Services and click that link.
5. In Key Management you will find a way to associate your key to the billing entity which I never used a credit card with I just selected the proper add billing and it took it, This is the part I can't show as it has permissons and key showing, so you have to take it on your own to do the right thing here.
6. I tried my old key from back when I started using Google maps and now it works.
Notice, also, at the top left of those images it now shows the $300 credit and the time limit, which I didn't have before I tried this. Hopefully this helps, I'm not able to give complete images and descriptions of each step as when I did the process none of the process stayed in the window, it changed as I went along.