Como o controle do PS4 tem um driver oficial da Sony no kernel há muito tempo, acho seguro dizer que o problema não está no controle.
Daí precisamos saber sobre o hardware de Bluetooth envolvido. Esses três sistemas (Fedora, Zorin e Windows) estão instalados na mesma máquina? Qual o hardware dela(s)? Acontece com outros dispositivos Bluetooth?
Outra informação que ajudaria seria a saída de sudo dmesg depois de tentar conectar o controle.
Acho relevante especificar se há dual-boot pois há relatos de placas Bluetooth que não funcionam caso você use um reboot “normal” (em vez de desligar e ligar de novo) para trocar de SO.
Só tenho esse tipo de mensagem de erro quando o controle está pareado num outro dispositivo e tento conectar no meu PC sem removê-lo da lista de dispositivos conhecidos e ligar o modo de pareamento novamente.