I was thinking to use the geonames location database and build a simple fuzzy search engine around it.
What wikidata objects are you referring to?
Maybe human settlement (Q486972) or city/town (Q7930989)? I haven't checked, but I would guess most of them have some coordinate location (P625), especially the bigger ones.