Find all instances of a given weekday in February for a given year
Java 8 Time APIs

Instead of the 'legacy' Calendar and DateFormat classes, you can rely on Java 8's new java.time.* APIs for more fluent chronology-related calculations.

For starters, your manually constructed Map can be replaced with a simple look-up on the DayOfWeek enum:

// scanner will be a wrapper over System.in
private static DayOfWeek getDayOfWeek(Scanner scanner) {
    String values = Arrays.toString(DayOfWeek.values());
    System.out.printf("Enter a day of week:%n%s%n", values);
    while (true) {
        try {
            return DayOfWeek.valueOf(scanner.nextLine().trim().toUpperCase());
        } catch (IllegalArgumentException e) {
            System.err.printf("Please try again with one of these:%n%s%n",
                    values);
        }
    }
}


The looping-validation ensures that only a valid DayOfWeek value is returned.

Next, you can use a couple of TemporalAdjusters to get the LocalDates you require:


firstInMonth(DayOfWeek): the first day-of-week of the month.
lastDayOfMonth(): the last day of the month.
next(DayOfWeek): the next day-of-week, i.e. 7 days from the LocalDate instance.


Then, with a helpful serving of DateTimeFormatter, the main processing logic can just be:

try (Scanner scanner = new Scanner(System.in)) {
    DayOfWeek dayOfWeek = getDayOfWeek(scanner);
    // getYear(Scanner) returns an int between the year range, MONTH = 2
    LocalDate first = LocalDate.of(getYear(scanner), MONTH, 1)
                                .with(TemporalAdjusters.firstInMonth(dayOfWeek));
    LocalDate last = first.with(TemporalAdjusters.lastDayOfMonth());
    DateTimeFormatter formatter = DateTimeFormatter.ofLocalizedDate(FormatStyle.MEDIUM)
                                                    .withLocale(Locale.GERMANY);
    for (LocalDate date = first; !date.isAfter(last);
            date = date.with(TemporalAdjusters.next(dayOfWeek))) {
        System.out.println(formatter.format(date));
    }
}


Other observations


It's not recommended to throw a generic Exception as it's... too vague. You can consider using IllegalArgumentException for invalid year inputs outside \$[1500, 2005]\$, as the exception type is then more defined.
More importantly, you shouldn't be throwing your own Exceptions and then catching it purely as a form of flow control.
HashMap&lt;String, Integer&gt; daysOfWeek = new HashMap&lt;&gt;() can be better written as Map&lt;String, Integer&gt; daysOfWeek = new HashMap&lt;&gt;(), to program to an interface rather than the implementation.
As illustrated above, you should also consider using try-with-resources on the Scanner instance for safe and efficient handling of the underlying I/O resource.