Si haces un doble `For Each` mostraras cada nombre con todas las edades almacenadas y no con la edad que le corresponde.
Tu código asume que los dos `ArrayList` contienen el mismo número de `Items` y que a cada nombre le corresponde la edad almacenada en el `ArrayList arrayEdad` en el mismo indice, asumiendo que esti se cumple siempre, el siguiente código debe funcionar bien, te recomiendo que lo pruebes y me comentas el resultado.

    Sub MostrarListado(ByRef arrayNombre As ArrayList, ByRef arrayEdad As ArrayList)
        Dim index As Int32
        index = 0
        For Each nombre In arrayNombre
            Console.WriteLine("La persona se llama: " & nombre)
            Dim edad As String
            edad = arrayEdad.Item(index)
            Console.WriteLine("y tiene: " & edad & " " & "anos")
            index = index + 1
        Next
    End Sub