Si tienes una aplicación de copia de seguridad, es posible que puedas hacer una copia de seguridad de los datos de la aplicación, sincronizarla con la nube y restaurarla en el otro dispositivo. La única vez que lo intenté hizo que Authenticator se bloqueara al iniciarse.
Si guardaste las claves secretas que te dieron, lo cual es una buena idea siempre que sean seguras y estén separadas de tus contraseñas, puedes volver a introducirlas en un nuevo teléfono buscando un generador de códigos QR seguro (uno local o basado en JS que no envíe los datos a ningún servidor) y formateando cada uno de ellos así:
otpauth://totp/LABEL:USERNAME?secret=SECRET&issuer=ISSUER&counter=N
Convierte eso en un código QR y Authenticator lo escaneará. O encuentra una herramienta que haga ambas cosas:
http://dan.hersam.com/tools/gen-qr-code.html
Si tienes algún código basado en un "contador", necesitarás saber cuántas veces lo has usado, lo que podría ser problemático, pero esos son bastante raros.
Si no guardaste los secretos, tu única opción es recuperar la base de datos desde la aplicación, ya sea desde una copia de seguridad o directamente desde el dispositivo. Está en:
data\com.google.android.apps.authenticator2\databases\databases
Puedes abrirlo con sqlite3.exe
o cualquier interfaz de usuario de SQLite.
sqlite> .headers on
sqlite> select * from accounts;
Obtendrás una tabla con los secretos, contadores, etc., que necesitas utilizar.
Si no puedes obtener la base de datos desde authenticator, entonces no tienes más remedio que utilizar cualquier mecanismo disponible para cada sitio. Es muy raro que un sitio te dé el secreto por segunda vez, generalmente lo mejor que puedes hacer es entrar de alguna otra manera, desactivar 2FA y volver a activarlo con un nuevo secreto.