Para cambiar el idioma de un toast se hace igual que con cualquier otro elemento.
Lo importante es que no definas las cadenas (strings) en el propio código fuente sino que lo hagas en el fichero strings.xml. Así después basta con crear otro fichero strings.xml cambiando el lenguaje y definir las mismas cadenas pero en el idioma que quieras.

Desde el código fuente tienes que hacer referencia a las cadenas de strings.xml. Así al cambiar el idioma del dispositivo, las cadenas se obtendrán del xml correspondiente y se cambiarán automáticamente.