Ich habe ein merkwürdiges Problem: Ich verwende ein Notebook mit Win 8.1 64-bit, Fritzbox 3490 hinter Kabelmodem, ein QNAP-NAS und einige andere Geräte im Heimnetz.

Mein Win 8.1 Notebook findet nach dem booten nicht immer meine Netzlaufwerke: Fritz.NAS und QNAP-NAS.
Ein anderes Mal werden die Laufwerk nach dem Starten wieder angezeigt.

Das scheint willkürlich zu passieren.

Als Firewall verwende ich die in Bitdefender Internet Security 2016 integrierte Firewall.

Woran kann das liegen?

Das kann schon an der Firewall von Bitdefender liegen.
Grundsätzlich rate ich von Desktop-Firewalls in Produkten von Dirttanbietern ab, weil die keinen echten Mehrwert bieten dafür aber zu oft Probleme machen und ein Laie mit der Konfig eh überfordert sein dürfte. Die Windows-Firewall ist da in dieser Hinsicht deutlich besser.

Was für ne Meldung kommt denn, sowas wie "es konnten nicht alle Netzlaufwerke wiederhergestellt werden?"

Das mit den Netzlaufwerken kommt manchmal.

Fehlermeldung gibt es überhaupt keine. Nur, wenn man den Fehler beheben möchte und dide Diagnose startet, kommt "Stellen Sie sicher, dass der Computer eingeschaltet und mit dem Netzwerk verbunden ist"

Der ist an. Über den Browser erreiche NAS und Fritzbox ohne Probleme.

hast du die laufwerke im explorer gemappt? wenn ja dort trennen, dann:

systemsteuerung > anmeldeinformationsverwaltung > windows anmeldungen

dort den zugang zum NAS hinterlegen, dann wird er als kategorie Unternehmen gespeichert und ist auch ausserhalb dieser einen Sitzung/Benutzeranmeldung verfügbar.