Windows 10: Cortana setup will not allow me to select Location

Thanks. Suggest running
SFC /Scannow
from an elevated command prompt
(Windows key + X, Command prompt (admin) )
This will take some time, but is worth doing as a check.

(You won't be able to turn Location on in Settings with geolocation not running, so we'll use the above to try to fix that- maybe - it also affects Cortana as you've seen.

"Interesting thing though, is that, when I logged in, it started to work, then the notebook icon disappeared and it asked for location access. I think the problem must be an application starting on startup,"
Now try a clean boot, and see if things improve.
How to perform a Clean boot in Windows 10 - TechNet Articles - United States (English) - TechNet Wiki

===============================================

Note the following:
Geolocation

After disabling the Geolocation Service by changing startup type to Disabled, attempts to re-enable it will fail with an error message. As the Geolocation Service can no longer be started, Geolocation will remain disabled on the device and prevent location based functionality from working. To work around this issue, manually delete the following regkey using regedit: HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\lfsvc\TriggerInfo\3.
)

Hi, please post as asked previously, what you have here:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\lfsvc\
- or as near as you can.

"A clean boot also doesn't work."
- I read that as meaning you booted successfully, but no change in symptoms.

As SFC /Scannow is ok (which is good, of course), and there's no obvious 3rd party conflict, and if you can't resolve this in the usual way (registry key) I suggest your final option is to do an in place repair install.

I have found a number of times people spend a long time seeking a specific solution to a specific problem, and this approach offers a solution to a lot of issues related to new Win 10 features (but not all, inevitably).

Here's how:
Repair Install Windows 10 with an In-place Upgrade - Windows 10 Forums
This keeps all your programs and settings except
- you may lose the odd file type association - but will keep almost all.
- system restore will be turned off- so enable it afterwards
- you will lose customised system icons (if any)
- you may need to reconnect your WiFi
- you will need to redo all subsequent Windows updates

This will take a couple of hours being a Windows install procedure, excluding time to download the relevant iso file.

It's a repair technique I regard as a strength of win 10 as each time a new upgrade is released, that's the point used for any subsequent in-place repair, so it's really generally worth downloading the iso each time.

You can explore what takes boot time and decide if you really need anything that adds significant time, but a clean boot also potentially loses a lot of functionality you've chose to have running. A compromise is to use hibernation (which must be enabled in order to be able to use Fast Startup, which uses the same storage area on disk).

One option is to use a SSD in place of a HDD for your OS and programs. (Hardware change), noting that some SSDs are much faster than others.