Cuando eliminás una página dentro de tu tienda (por ejemplo, un producto, una página de contenido, una categoría, etc.) el enlace o URL a esta puede permanecer en el índice por motores de búsqueda como Google, ya que la renovación de esta información no es automática.
Google guarda esas URLs en su índice y, cuando ya no existen, intenta acceder igual y por eso muestra un error 404:

¿Cómo solucionarlo?
1. Si ves un resultado como este, justo debajo Google suele mostrar un texto como “Corregir problemas de indexación de página” o “Ver detalles en Search Console”. Hacer clic en ese texto para ir a Google Search Console.
Allí, podés observar qué URLs están dando error.
2. Enviar un sitemap a Google para que vuelva a rastrear tu tienda y descarte las URLs antiguas. Podés ver cómo hacerlo en el siguiente tutorial:
¿Cómo enviar un Sitemap de mi Tiendanube a Google?
¿La corrección es automática?
No. Una vez enviado el sitemap, Google necesita un tiempo para volver a rastrear tu sitio y actualizar su índice. El plazo habitual suele ser entre 48 horas y 2 semanas, dependiendo de la frecuencia con la que Google visite tu tienda.