Based on the info kindly provided by @Mike, I was able to make this work again. There were several changes required, in case somebody else runs into the same problem.

Change the Map Tile URL

https://{1-4}.base.maps.ls.hereapi.com/$maptile/2.1/maptile/newest/$normal.day/{z}/{x}/{y}/256/png?apiKey=${YOUR_KEY}&lg=eng

must be changed change to

https://maps.hereapi.com/v3/base/mc/{z}/{x}/{y}/png?size=512&apiKey=${YOUR_KEY}&style=explore.day&lang=en

• 512x512px tiles are used
• the tile style is now provided via a separate style parameter
• style names have changed, e.g. from normal.day to explore.day
• the language parameter has changed from lg to lang and uses two-letter codes (en) instead of three-letter codes (eng)

Add the TileSize Parameter When Constructing the Source

source: new ol.source.XYZ({
  tileSize: [512,512],
  url: `https://maps.hereapi.com/v3...
  ...

so OpenLayers knows that we use 512 pixel tiles.

Old Keys and New Keys

API keys created by users years ago still work fine with the new API versions. But new keys acquired recently only work with the latest API versions.

Restrictions

The amount of free daily requests has been reduced significantly for new keys. Even when you are only testing things, you'll run into the 'too many requests' error quite quickly now. Adding a credit card or Paypal to your account will increase the amount of free daily requests again to a usable level.