The problem seems to be something with ATmega16U2 and USB circuits, FW etc. It has nothing with ATmega2560.
Are you sure the USB-C is connected correctly?
I've never used USB-C but according some designs on the internet A5 B5 should be tied down to GND via 5k1 resistors.
Your schematics is not clear for me, plus it is too small.
That has nothing to do with the board detection. Missing that will result in not being able to upload but board detection is an issue with the 16U2, cable or PC.
Even if the connection is in USB1.1-2.0 mode? USB-C as I know only gaives possibility to use USB3.0 Protocol, but if master both sides useing USB2.0 those pins does nothing.
I'm not sure. As I wrote, I'm not familiar with USB-C but maybe it is way how to force USB 3 to USB2. It is "Configuration Channel".
It is definitely an issue with USB-ATmega16U2-firmware16U2.