How is USB-C able to be used for DisplayPort, Headphone jacks, OTG etc?
How is USB C able in practice to be so polyvalent?

It was designed that way. And because it has multiple wires/channels that can be reconfigured as needed.

Do all the converters communicate with the port using a single protocol like HID to register their type and bring up the appropriate driver and message format? How is it implemented roughly?

I wouldn't say all. Some will use standard usb data for whatever they need while others will use USB C alternative modes. This can be triggered by simple resistors or by side channel communication like on the CC pins. There is no one communication type.

How is USB C able to route high speed video signals from graphics cards with minimum latency while being multiplexed for other uses?

Afaik it doesn't multiplex all mode videos at the same time as usb 3 connections. Once it switches modes it stays that way. It may allow usb 2 connections. Different pins. Usb video is a different thing and that would work like any other usb data implementation.