Hola tu problema es que estas reemplazando la variable a1, a2
public static void main(String[] args) {
String a1 = "aa";
String a2 = "bb";
String a3 = "cc";
String a4 = "dd";
String[] dato = {a1, a2, a3, a4};
for(int i = 0; i<3; i++){
String a5 = ("a"+ i); // esto no deberias hacer
System.out.println("a"+i +"= "+a5"+dato[i]);
}
}