Resumen del problema
La opción «Quitar la base de la categoría (normalmente /category/) de la URL de la categoría» del plugin Yoast SEO no funciona con WPML.

Cuando activa esta opción en el plugin Yoast SEO («Quitar la base de la categoría (normalmente /category/) de la URL de la categoría»), las categorías en otro idioma dan errores 404.
Solución alternativa
Este problema está solucionado. Actualizar a la última versión lo soluciona en su sitio, por lo que solo necesita esta solución alternativa si aún no puede actualizar.
Deshabilite esa opción en el plugin Yoast SEO y use este plugin en su lugar https://wordpress.org/plugins/no-category-base-wpml/ (se abre en una pestaña nueva)