Has reprogramado al montar el filtro?
En cuanto a kms no te sabría decir pero supongo que depende del ambiente en el que te muevas convendrá lavarlo más frecuentemente o menos independiente de los kms que le hagas al coche.
Desde el desconocimiento te diría de lavarlo cada 10k kms como el cambio de un filtro normal pero vaya, en tema filtros es obvio que cuanto más limpio esté mejor así que si le pegas un repaso antes de esa cifra yo creo que daño tampoco le hará.
Pd: edito ya que me he liado pensando en el filtro de aceite pero mantengo la cifra, lo que haría sería en el cambio de aceite y filtro de aceite, limpiar el de aire ya que estoy