First, start learning the language. Then ask if you can go along for lunch. Let them know that they should continue to speak in their language at lunch and that you are trying to learn. Be light hearted about it and accept any help they offer. This will build bonds.

If you don't want to learn the local language, then perhaps you should start looking in companies or countries that do speak your language primarily. I would think there's a high chance of encountering a similar issue again if you stay in that location.

Also, start implementing some standards like meeting agendas and action items. This is the type of stuff a lead should be setting the standards on.