Wouldn't you have to "consent" first?

What if you didn't and did not proceed with the process? Can you complain still?

As in - if you didn't give your consent there's no violation has occurred and they don't have your data, so nothing to ask for?

That's a bit more complex.

Everyone is free to make a tip to DPA. However DPA is free to decide if they want to start their own investigation based on that unlike when you make Article 77 complaint.

There isn't a lot of case law around the threshold of Article 77. The text says "if the data subject considers that the processing of personal data relating to him or her infringes this Regulation". If read completely alone one could make argument that since you didn't consent no processing occurred -> you do not have right to make an Article 77 complaint.

However when taking the in account the goals and purpose of GDPR as well as recital 141 I would argue otherwise. To be specific recital 141 says "if the data subject considers that his or her rights under this Regulation". CJEU also often refers to GDPR's objective of ensuring high level of protection of fundamental rights and freedoms of natural persons. I feel that ex post requirement would be quite contrary to that.

Due to this my personal stance would be that just offering invalid consent choice where refusal has negative consequences is something that violates data subject's rights even if processing didn't occur and would be eligible for actual Article 77 complaint rather than just tip to DPA.

[EDIT] Also, there is Article 82 path via damages. In your case you could potentially argue that you suffered damages (like lost wages) due to company's invalid consent requirement. This, however, is generally a lot harder and more expensive path. Depending on how legal costs are allocated in your jurisdiction you could also end up with judgement where you need to pay your opponent's legal costs if you lose.

For Article 82 claim you almost definitely will need a lawyer.