I found out that the router needs to be set to include the WLAN standard '''802.11b''' in order to connect the printer (HL-2135w) via WPS.
My router was set to 802.11g+n which is fine for printing via WLAN once the printer has received the credentials of the WiFi network. The router tells me that the printer is using 802.11g within the network.
But apparently the printers WPS mode is only working via 802.11b. When I set my router to '''802.11b+g+n''' the first connection attempt was successfull.