Абсолютно корректен перевод "Они идут за конем" в значении "следуют". Такой формальный подход некорректен, потому что приучает к неправильному переводу.
И кстати, почему нельзя сказать "лошадь"? В русском языке это видовое название, а слово "конь" - литературно-патетическое", также, как кошка - это видовое название, а кот - ну, скажем, бытовое. Негибкие составители.