В предложении «Когда он пришёл, мы уже ушли» запятая стоит правильно: союз «когда» вводит придаточное предложение времени, которое отделяется запятой от главного (независимо от порядка частей): «Мы уже ушли, когда он пришёл».
Краткие правила и примеры.
$1$ Запятая ставится, если «когда» вводит придаточное предложение времени (сложное предложение).
- Когда он пришёл, мы уже ушли.
- Я не знаю, когда он приедет.
- Тот день, когда всё началось, запомнился надолго.
$2$ Запятая не ставится, если «когда» — не союз, а обстоятельственное наречие в простом предложении (вопрос, побуждение, ответ и т. п.), то есть внутри одной грамматической основы.
- Когда ты придёшь?
- Мы гуляли тогда, когда было тепло. (здесь запятая только разделяет однородные члены, но не отделяет придаточного от главного — смотрите контекст)
$3$ Особые случаи:
- Повторяющийся «когда» при перечислении (однородные обстоятельства): запятые ставятся между частями, но не перед первым «когда»: «Он появлялся когда утром, когда вечером.»
- Сложносочинённые/сравнительные конструкции типа «тогда как» обычно отделяются запятой: «Он работал, тогда как она отдыхала.»
- В сокращённых/эллиптических ответах возможны другие знаки (тире): «Когда? — Не знаю.»
Итог: если «когда» вводит придаточное (время) — ставим запятую; если это наречие в одном простом предложении (вопрос, внутренняя обстоятельственная единица и т. п.) — запятая не нужна.