Você precisa instalar o PackageKit-command-not-found
package:
dnf install PackageKit-command-not-found
É bom verificar sua configuração /etc/PackageKit/CommandNotFound.conf
para alguns detalhes (está bem documentado), mas a configuração padrão deve ser suficiente.