Apparently, my previous post didn’t make it clear which behaviour I expected and why the behaviour I observed was confusing to me.
In short:
As a user, I’d expect the Search feature (in the page header) and the Autocomplete features (for creating page links etc.) to search exactly the same contents which I can see myself in the Wiki.
If my Wiki is configured to display language X, then I’ll see the translated version of pages which have such a translated version, and I’ll see all pages which do not in their default language. But I’ll see all of this content in the navigation tree, breadcrumb and so on.
However, this is not the content the Search and Autocomplete features will work on by default - both only will search pages which actually have a translation to language X and will simply ignore all the other content which I can see in the Wiki.
This also means that I will not be able to use auto-completion for creating links to pages which have not (yet) been translated…
According to XWiki professional support (Thanks for the quick reply!), this behaviour is actually intentional - even though I still don’t really understand in which case it may be the behaviour expected by the user. 
In any case, the professional support pointed me to Loading... which describes this problem. The search behaviour can be adjusted with some code changes in some internal XWiki pages which implement the search and auto-suggest features.
Adjusting the search is described here:
https://jira.xwiki.org/browse/XWIKI-9977?focusedCommentId=79695&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-79695
Enabling this search behaviour for auto-completion apparently requires another change in
/xwiki/bin/edit/XWiki/SuggestSolrMacros
where the following two lines:
#if (!$filterNames.contains('locale'))
#set ($discard = $filterQuery.add("locale:(""$xcontext.locale"" OR """")"))
have to be changed to:
#if (!$filterNames.contains('locales'))
#set ($discard = $filterQuery.add("locales:(""$xcontext.locale"" OR """")"))
A third adjustment might be necessary somewhere, but I’m not yet sure about this. In any case, Search and Autocompletion work more as I’d expect with those adjustments applied.
I guess this should be added to the FAQ or Snippets documentations - would it be correctly located as an FAQ?
Some pages are sometimes found twice in the search, though. (I observed this with a page which only had a German language version as default language, and this single version of the page was listed twice in the Search results, once indicating locale “de” and once “de_DE” - strange…)
This is not would not be what I’d expect (There is only a single language version of this page, and as a user, I also see the page only once in the navigation tree, so why display the same translation of the same page twice in the search results?), but it’s still better than not being able to use Search and Autocomplete for a majority of pages in the first place…