Las preferencias de los atajos de teclado de Catalina carecen de "acceso completo al teclado".

La interfaz de usuario simplemente se cambió en Catalina. En Catalina, marcar "Usar la navegación del teclado para mover el foco entre los controles" es idéntico a seleccionar "Todos los controles" en Mojave. Desmarcar "Usar la navegación del teclado para mover el foco entre los controles" en Catalina es idéntico a seleccionar "Sólo cuadros de texto y listas" en Mojave.

Puedes confirmarlo usando Terminal en ambas versiones de MacOS y viendo los cambios en la salida de defaults read (redirigir la salida a un archivo y diferenciar los dos archivos). El cambio de los botones de radio en Mojave y la activación/desactivación de la casilla de verificación en Catelina sólo cambian la siguiente preferencia:

defaults read "Apple Global Domain" AppleKeyboardUIMode

Cuando se marca "Usar la navegación del teclado para mover el foco entre los controles" (o se selecciona "Todos los controles") el valor es 2. Cuando no se marca "Usar la navegación del teclado para mover el foco entre los controles" (o se selecciona "Sólo cuadros de texto y listas") el valor es 0.

Esto no tiene nada que ver con el control total del teclado. Para hacer que el foco se mueva a los resultados de la búsqueda en lugar de moverse por los controles, el atajo de teclado por defecto es usar opción + tabulador. También se puede cambiar este comportamiento en las preferencias de Safari -> avanzado -> pulsar tabulador para resaltar cada elemento de una página web como se muestra en la imagen adjunta.