From same source: "The processing must be necessary to deliver
your side of the contract with this particular person."
That is - these regulations refer to the performance of a contract by the service provider. If the data isn't necessary for creating the sandwich, you're not allowed to deny use of the service based on the user not giving you the data.
GDPR was specifically written by smart lawyers and regulators to prohibit the specific kind of contract you're describing. The whole point of regulations like this (also minimum wage, regulation of arbitration agreements, etc.) is to limit the kinds of contracts people can enter into.
Specifically, they're allowed to consent to give you that data, but that's not allowed to be a condition for the use of the service.
EDIT: More specific sourcing on the way that GDPR regulates contracts, in Article 7(2): "Any part of such a declaration which constitutes an infringement of this Regulation shall not be binding."
EDIT 2: And in fact, we've gone in a circle. Again, as Recital 43 states: "Consent is presumed not to be freely given if it does not allow separate consent to be given to different personal data processing operations despite it being appropriate in the individual case, or if the performance of a contract, including the provision of a service, is dependent on the consent despite such consent not being necessary for such performance."
This is all super crystal clear, by design.