Get the sdk-tools.zip from the Mini-SDK post -
http://androidforums.com/threads/adb-guide-updated-2014-11-11.443072/#post-5389081
If you've ever run HTC Sync or could see your phone storage on your pc, you ought not need anything else.
Unzip sdk-tools.zip, it'll create an sdk-tools folder. Shift + right click on the sdk-tools folder, Menu, open command window here (or similar words) - do that.
Get phone to FASTBOOT at the top (from your picture, tap power to select the FASTBOOT menu item), plug in to PC, it should change to FASTBOOT USB.
Command window say -
fastboot oem relock
Confirm that the top of the screen says LOCKED.
Reboot back to FASTBOOT USB mode if not sure.
If it doesn't say LOCKED then try -
fastboot oem lock
STOP IF YOU CAN'T GET THE PHONE LOCKED.
Get the right update for your phone from here.
http://www.htc.com/us/support/rom-downloads.html
Was this your phone originally? Are you unsure what carrier it was originally on? (I'm trying to guess why you didn't answer that question - you missed it?)
If it's from AT&T then you want this -
http://www.htc.com/us/support/htc-one-m8-att/news/
If it wasn't, you might want to stop and let me know before trying that version.