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