Welcome TimB! Glad to see you made it to the forums.
The top Navigation bar contains three language specific links: Sale Items, Gift Certificates, and Home (Home being visible on mobile devices). The rest are the names of Categories that you have created -- in English.
Now that you have another language installed and enabled, you can now use the Translate function.
In admin, Categories, click the Edit icon for a category. On the editing screen, click the Translate tab. Click "Add Translation".
On the page that is shown, choose the language for this translation and enter new data to be shown for this category when the storefront is showing that language.
Once finished and Saved, be sure to Clear the Cache.