Is it connected to the internet?
Yes, it is connected to the internet.
I guess it is as @Chastagnet wrote, some other lock is on it. You are not the first one with such an issue.
Maybe also try with the flashtool which is mentioned before. Good luck with your investigation.
There’s your answer. As an American I can tell you Verizon is the worst carrier in the USA, full corporate hostility. Their service is awful not only by way of the phones they provide, but in every other way as well. Verizon does not provide carrier unlocking and I expect they block OEM unlocking as well. Generally you want to avoid any US carrier provided phone, best to buy carrier unlocked through retail.
Thank you all for your support, I’ll try with the flashtool again and for the future I now know that buying a used phone can have some risks here.
Thank you mihi and CraigHB.
Sometimes a device for example from Samsung can have diffrent CPU’s on the market and one version is possible the other one isn’t. Just another example what to look out for 
Good luck
I suggest you look very carefully on the outside of the phone for device and model information and especially any indication that it might have any carrier mentioned.
Then in Settings > About phone … Android version … and look in as many sections as possible for Software information and phone specification looking for any clue whether you are running a carrier or in any way non regular device.
And follow the links above for clues why you see this locked state.
You might contact the agent who performed this. Were you able to tell if the phone was Factory reset? If yes, maybe the agent was at fault by not supplying a fully open build.
I have done many Canadian Pixels and never run into an unlock issue with one. I have not done the 4A only above 5 but should still apply.
I see you have done some phones before but silly question is developer mode enabled? Unsure if developer mode has to be on to see OEM unlock switch. Maybe developer mode got turned off somehow?