Nexus 5. Needs factory reset, no access to AndroidOS., can't unlock or grant permission
First, I want to clarify:  when you hold the volume button while turning on the phone, and get the screen with the big "Start" arrow at the top, that's not recovery mode.  That's the bootloader, also known as fastboot mode.  When you choose "recovery mode" from the fastboot screen and get a screen with a little droid and a red exclamation mark, that's recovery mode.  adb commands work only in the regular OS or in recovery mode; fastboot commands work only in fastboot mode.

You don't need to worry about enabling USB debugging from the settings menu; that's only for enabling it within the regular Android OS.  It's always enabled in fastboot and recovery mode.  Also, adb reboot bootloader is the same as just turning the phone off and then holding the volume button when turning it back on again.

The factory reset that you already did should have fixed the problem.  That erases all installed apps, files, etc. and leaves you with just the OS, which is in a read-only partition and shouldn't have been affected by any apps you installed.  If the problem persists after a factory reset, either the app somehow managed to gain root and modify the system partition (unlikely if you were running 5.1, assuming you hadn't rooted it), or it's a problem with the phone itself and the timing (after you installed that app) was just coincidental.  Maybe something went wrong while installing the 5.1.1 update.

Anyway, the best course of action now is to reinstall the factory image.  This is more thorough than a factory reset because it actually reinstalls the OS itself, rather than just erasing all the user data.  If the system partition is corrupted somehow, a factory image will put it right.

Go to Google's Nexus factory image page and download the 5.1.1 image for the Nexus 5.  At the top of that page, you'll find directions for how to install it.  In a nutshell:  put the phone into fastboot mode, then run fastboot oem unlock, then run the flash-all script included in the factory image package.

The fastboot program on your computer may require administrative privileges, so you should run it as root when doing fastboot oem unlock.  You should also run the flash-all script as root, since the script just runs several other fastboot commands for you.

Just to be clear:  installing a factory image will erase all user data stored on the phone.  Don't do it if you have any important data on the phone that you don't want to lose.  (But if you already did a factory reset, you probably don't have any data left on the phone anyway.)