"Device only" location not working on Moto G

[AC Question]

I have a Moto G first generation with Android 5.1.
When I set the Location Mode to "Device only" (Use GPS to determine your location) the phone is unable to detect any location. I've tried to download GPS Status & Toolbox, and the GPS does not seem to be answering.
What can I do?

Thanks