Segue abaixo a minha implementação do for. Consegui chegar nessa solução a partir do post de um colega aqui do forúm, me ajudou a entender como iterar sobre esse tipo de conjunto que armazena chave e valor.

        public class TestePessoaIdade {

    public static void main(String[] args) {

    Map<String, Integer> nomesParaIdade = new HashMap<>();

        nomesParaIdade.put("Paulo", 31);
        nomesParaIdade.put("Adriano", 25);
        nomesParaIdade.put("Alberto", 33);
        nomesParaIdade.put("Guilherme", 26);
        nomesParaIdade.put("Edson", 36);

        for(String keys : nomesParaIdade.keySet()) {
            System.out.println(keys);
        }

        for(Integer values : nomesParaIdade.values()) {
            System.out.println(values);
        }

        for(String key : nomesParaIdade.keySet()) {
            System.out.println(key + " - " + nomesParaIdade.get(key));
        }
    }
}