How to enable tokens for custom entity?
I had the impression that in Drupal 8 all entity tokens are provided
  automatically since it uses the new field structure but I don't see
  anything available for my entity.


That impression is wrong. Drupal (core) doesn't provide any generic tokens for entities, all that are in core are hardcoded.

Now, token.module, just like in D7, provides some tokens for configurable fields. Simply because the existing functionality was ported to D8. It is possible to extend that to all fields and it shouldn't even be that hard. In fact, there's an explicit check that ignores anythig that's not a configurable field, so we just have to remove that and see what happens.