Here is the solution. Boot into fastboot menu, choose 'recovery' with volume down and then press volume up. If you see the lying Android Robot press and hold the power button and both volume buttons together for 2 seconds and release them again. Seems to be a bug under KitKat, because under JB I was able to boot into recovery directly from fastboot menu.
Sent from my Nexus 7 2013 using xda app-developers app