Assuming you stick with add_rewrite_rule(), if language and title where set as meta data on the /en/ post, then you can simplify the search down to a simple WP_Meta_Query() for /:lang/:title/ and pull the actually ID of the translated post there.
Translations for /en/best-restaurants-in-tokyo:
"/it/migliori-ristoranti-a-tokyo" => 4016"/fr/meilleurs-restaurants-à-tokyo" => 4017