MENSAJE REGISTRO NO ENCONTRADO PHP

mysqli_fetch_array() devuelve false solamente si hay errores, para verificar si hay filas tienes que usar mysqli_num_rows().

Puedes hacer una verificación en un sólo if con algo como esto:

if ($res && mysqli_num_rows($res) > 0)

Creo que tu código se puede simplificar un poco más, veamos:

#Conviene verificar los POST, usaremos un ternario
$cedula= !empty($_POST['cedula']) ? $_POST['cedula'] : NULL;
if ($cedula) {
    $conn = mysqli_connect($db_host,$db_usuario,$db_password,$db_nombre);
    #Cambio de método (ver punto 3 de recomendaciones al final)
    $res = mysqli_fetch_row(mysqli_query($conn,
                 "SELECT primer_nombre, primer_apellido from nacional where cedula='$cedula'"));
    if ($res && mysqli_num_rows($res) > 0) {
        $outPut=utf8_decode($res[0]). " ".utf8_decode($res[1]);
    } else {
        $outPut="No se encontraron registros";
    }
} else {
    $outPut="No se mandaron datos en el POST";
}
#Construimos el PDF y usamos $outPut
$pdf=new FPDF('L','mm','A4');
$pdf->AddPage();
$pdf->Cell(0,0,$outPut,0,1,'C');
$pdf->SetFont('helvetica','',12);
$pdf->SetTextColor(0,0,0);
$pdf->Text(15,195,utf8_decode($fecha));

En el código no se ve de dónde sacas el valor $fecha, por lo que es imposible saber por qué no muestra el dato correcto.

---

Algunas recomendaciones

1. Deberías evitar la ejecución de consultas que incluyan valores dinámicos como $cedula, cualquier usuario mal intencionado podría manipular ese dato y hackear el servidor mediante lo que se conoce como Inyección SQL. Cuando puedas lee sobre ese tema y procura blindar tu código. Para más detalles consulta la pregunta: ¿Cómo evitar la inyección SQL en PHP?
2. El uso constante de utf8_decode() puede (y debería evitarse) mediante una configuración adecuada de la codificación a nivel de servidor, de base de datos, de conexión y de HTML. Para más detalles revisa la pregunta: ¿Por que el Carácter inspector (�) aparece en algunos datos obtenidos de la Base de Datos?
3. mysqli tiene diferentes métodos de lectura, conviene siempre usar el método adecuado según el tipo de lectura que vas a hacer. Dado que mysqli_fetch_array devuelve los datos como array asociativo Y numérico (o sea, dos veces los mismos datos ordenados de dos formas) es mejor usar un método específico según el tipo de acceso que usarás para los datos. Dado que usas el acceso por índices numéricos, es mejor usar mysqli_fetch_row, que trae los datos una sola vez, como índice enumerado. Así evitamos cargar la memoria con datos adicionales.

Puedes chequear el resultado de mysqli_fetch_array ($res). Si es nulo, significa que no hay registros (ver https://www.php.net/manual/es/mysqli-result.fetch-array.php)

$res = mysqli_fetch_array(mysqli_query($conn,
             "SELECT primer_nombre, primer_apellido from nacional where cedula='$cedula'"));
if (!$res){
   die("ID no encontrado");
}

Ademas recomiendo chequear primero que la consulta en mysqli_query() sea exitosa (retorna un recurso valido, de otra manera retorna FALSE) y luego realizar el fetch:

$resource = mysqli_query($conn,
             "SELECT primer_nombre, primer_apellido from nacional where cedula='$cedula'");
if (!$resource){
  // error en la consulta
   die(mysql_error($conn));
}
$res = mysqli_fetch_array($resource);
if (!$res){
   // no hay datos
   die("ID no encontrado");
}