BMW, Audi and Toyota cars can be unlocked and started with hacked radios

How would you prevent this type of attack while retaining the keyless start and entry feature? (just curious)

Speaking from experience (locksmith), you cannot download the skills required to use a slim jim. Well, you kinda can, being that there are books/catalogs that show you where the lock's internal mechanism is, but being able to manipulate it requires more than simply pressing "exploit car radio".

Yes!

Also, the link ought to be fully authenticated and end-to-end encrypted. And one could require the user to press a button on the key fob.

Lots of ways. The ECU only goes into pairing mode if it gets a valid challenge-response from the manufacturer. If put into that mode, it provides a nonce encrypted with its own pairing mode public key that only the manufacturer knows (could even base-64 encode it and show it on screen to let people do this over the phone). You could make it two-phase where it requires the first response within 5 minutes of starting, then requires a second response that must come one hour later (also with a 5-minute entry window). This makes social engineering much more difficult and the delay makes it impractical for most car thieves, but it won't impact dealers or legit owners at all. If the registered owner provides a cell phone, the first attempt should send a text message to let them know the ECU will enter pairing mode and allow them to reply with "STOP" to cancel any further requests.

Once in pairing mode, the physical key and ECU use standard public-key crypto (ala SSL) to setup a secure connection, then exchange keys.

In theory you could allow boot-strapping another key so long as an existing paired key is present which would make the procedure above your failsafe for when all keys are lost/destroyed. If you wanted to take things a step further you could use a form of distributed Kerberos where the manufacturer sets up a physical key with a ticket allowing access to one (or a set) of allowed cars but that makes the manufacturer's systems a massive target for hacks/social engineering which is a problem because thousands of dealer technicians need access to those systems... that's the point of the delays and short acceptance windows above. An evil tech or hacker can't pre-create a bunch of keys on the sly.

To unlock or remote start, the key broadcasts a HELLO message, encrypted with the ECU's public key. The ECU responds with an ACK+nonce encrypted with the physical key's public key. The physical key decrypts it and replies with an ACK+nonce encrypted with the ECU's public key. Congrats, you now have a reasonably secure system that prevents replay attacks.

Ultimately it would require embedded software engineers and company management who a) understood security and b) gave a shit. Both are in extremely short supply.

Not the OP, but having owned a 30 year old car up until recently, I can list a few things I loved about it:

1. It operated on mechanics that I could see and touch and fix with a wrench, as opposed to opaque black box computers. I did not need a code reader to diagnose problems.

2. Thanks to point #1, I had the confidence in the knowledge that it was maintained correctly, the parts were good and soundly installed, that every bolt was tightened to the right torque specification, because I did quite a bit of it myself, and could visually inspect any work that someone else did.

3. Points #1 and #2 let me learn a hell of a lot about car maintenance and how everything works than you can with today's computers-with-wheels.

4. It was built years before every manufacturer decided to make their cars look like identical bars of soap, so it had a distinctive '80s look that you don't see much of anymore.

Sadly, the state of California decided that the car had to meet emissions standards that were far stricter than anything the original manufacturer ever dreamed of, so it eventually became impossible to smog. I had to sell it to someone outside the state and I'm currently driving a boring bar of soap.