Do GDPR/Data Protection regulations conflict with "No Privacy At Work"?

NB: This isn't Law SE so I'm going to simplify things a bit into more lay-terms.

There's a pretty big misconception here. Firstly (and arguably the most important) the thing to realize is that consent is not the only lawful basis for processing personal data.

In fact it is only one of the six lawful bases - and in broad terms it's very rarely going to be the one in play for an employer/employee relationship.

Depending on the exact nature of the Personally Identifiable Information (PII) it is far more likely to be "Contract" (i.e. your contract of employment) or "Legal obligation" (i.e. the personal information they are obliged to keep on employees to do payroll such as PAYE in the UK) or "Legitimate interests" (i.e. they need your personal info as part of doing business with you as an employee, e.g. your name in a work e-mail address, listing you in the internal phone directory, monitoring internet activity for security etc)

how does that sit with a typical "you have no privacy while using a company-owned device; we may collect anything" policies

Clearly the intention behind you using a company-owned device or service (such as e-mail) is to carry out your duties as employee, so if your PII is (almost inevitibly) ending up in the company's devices and systems as a result then that's going to come under one of the above non-consent bases. If you know (or could be reasonably expected to know) about such a policy, and then choose to put more of your personal info on there the is needed as part of your job - maybe you like to keep a dream journal about your recurring dream of joining Taylor Swift on stage at the Grammies and singing Wonderwall or something in your e-mail drafts or something. Well then it's a not really a GDPR thing, they didn't make you do that, and while there are some legal protections in the EU around stopping your employer from directly reading "obviously private" communications, even if it's on a work e-mail system you can't ask them to delete it saying you didn't consent.

That's like spray-painting your phone number on the office wall and demanding they paint over it.

I mean they would be in trouble if they demanded you store your dream journal on there - because they don't have a carte-blanche to all your PII, just the stuff they need and the stuff you freely give them.

So really this all boils down to the tried and tested advice - keep personal stuff off work-owned devices unless you're happy for work to potentially see it. Assuming that they store/read/etc everything you do on the company device is an intentionally extreme point of view to get you to play it safe rather than a direct reality.

So to sum up:

Can consent be denied or withdrawn by the employee?

If it's being collected/processed under one of the other lawful bases - No.

Where does the company policy surrounding employee use of their devices sit then?

Right where it always has (more or less). If anything a policy that discourages putting non-work necessary personal data on company devices is positively encouraged under GDPR, a well-crafted policy will reference the basis they are using for collecting/processing PII resulting from employment-related use of the device and they have just as much right to store/read/whatever your work-related communications as they had before.

If a company is looking to implement a GDPR/Data Protection policy that applies to staff as well as customers

Staff and Customers will be treated differently - even if they are under an overarching policy.

does it then mean that company devices may not collect various details if the user refuses consent?

No, any PII you end up putting on a company device over and above that required in the course of your duties is on you. You can "refuse consent" by.. not giving the data.

Does (threat of) action as a result mean that it can be claimed consent is not freely given?

This is actually one of the reasons why consent is not really a workable basis for collecting PII of employees, even in a free labor market there's still the potential for a power imbalance - it's partly why other bases exist in the first place and also why they can't ask you all sorts of invasive questions and rely on "consent". Things like the contractual and legitimate interests bases have to be reasonable or they can get challenged and the company can get some nasty legal consequences. So "what's your name and bank details so we can pay you" is going to be fine, "what's your favorite sexual position and cup-size" probably isn't. Likewise what they do with the information matters - it has to be in accordance with the lawful purpose for which they collected it - so they can use your home address to send you work communications, but they can't use it to turn up on your front lawn at 2am and boom-box Careless Whisper while pleading for you to date them or worse.. sell it to those people who turn up at your door and try and sell you double-glazing or over-priced vacuum cleaners.