Yo lo hago así.
Teléfono apagado, conectar s pc, esperar que acabe la animación de carga de bateria entonces apretar power y subir volumen, cuando aparece el logo de Samsung soltar los botones y entra en recovery.
Hace tiempo que no entro, luego en casa lo pruebo, pero de esa forma limpie caché algunas veces.