Hola Ariel.
En general el código está bien y da el resultado que se pedía.
Lo único que en el enunciado se pedía que paises y ciudades se almacenaran en un mismo array cuyo primer índice sea el número asignado a cada país y el segundo índice el número asignado a cada ciudad.
Una posible solución teniendo ésto en cuenta sería:
import java.util.Scanner;
public class Paises {
public static void main(String args []) {
String [][] arrMulti =new String[4][4];
String ax="";
Scanner ingresoTeclado = new Scanner(System.in);
for (int i=0;i<4;i++){
System.out.print("Introduce el nombre del pais "+(i+1)+" : ");
arrMulti[i][0] = ingresoTeclado.nextLine()+":";
}
for (int j=0;j<4;j++){
for (int i=1;i<4;i++){
System.out.print("Introduce el nombre de la ciudad "+(i)+" del pais "+(j+1)+" : ");
arrMulti[j][i] = ingresoTeclado.nextLine();
}
}
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
ax+= arrMulti[i][j]+" ";
}
ax+="\n";
}
System.out.print(ax);
}
}
Un saludo