Fines. No one should cross roads/paths randomly, with or without headphones.

One large fine, and people will learn.

No, they won't, punishment is never better than good design that incentivises and directs how something ought to be used.

Jaywalking is even a misdemeanor in some areas of the USA, it doesn't stop it from happening at all.

That would never work. Have you never been mindlessly walking and stepped on a bike way without realizing? Cities are for people after all. There's also so many places where bikes and pedestrians share the way, like roads under construction, and shared streets. We need to stop thinking of cities as these perfect automated places where humans are not welcome.