In this example, lets call the content entity a 'set' and the bundles a 'set type'.

Create the bundle configuration entity

As we wanted this content entity to support adding new bundles via the UI, a configuration entity makes sense to allow site-builders to create the various bundles as required, so we created a new configuration entity called 'set type' as per the examples, although we used a route provider instead of a routing file. We made sure to add the bundle_of annotation to the config entity.

bundle_of = "set",

Updating the content entity's annotation and fields

Once this was done, the next step was to update the content entity's annotation. We added the 'bundle' key and the 'bundle_entity_type' annotation

bundle_entity_type = "set_type",

*   entity_keys = {
*     "id" = "id",
*     "label" = "name",
*     "uuid" = "uuid",
*     "uid" = "user_id",
*     "bundle" = "type",
*     "langcode" = "langcode",
*   },

We didn't need to add a new field for our baseFieldDefinition to our content entity because we just deferred to the parent implementation. But we made sure to match up the description, label etc as desired - and that we called setInitialValue. As we're planning to add a new column to the entity's tables in the database, we need to populate the type column for existing records. Now with entities that don't support bundles, Drupal defaults to the entity ID for the bundle. e.g. for the 'user' entity, the bundle is always 'user' because User entities don't support bundles. So we knew our existing 'set' entities would have to have a bundle of 'set' too. But our new ones could have whatever we liked. So this is why our field definition for 'type' had to have look like so

$fields['type']->setInitialValue('set')

Update hooks to get everything in place

Since Drupal 8.7, support for automatic entity updates has been removed, so whilst adding the field, entity keys and updating the annotation works for a new install (hint, there won't be one) it doesn't help our existing production and QA sites - so we need an update hook to bring our existing entity-type and field definitions into sync with the code versions, which also takes care of the required database table changes.

So the steps we need to do here are:

1. install the config entity type
2. create a new instance of it for the existing entities
3. add the new field definition for the type field to the content entity
4. update the content entity definition

Installing the config entity type

The docs for installing a new entity type make it clear what we need to do. Our code ended up something like this:

/**
 * Adds the set type.
 */
function your_module_update_8001() {
  \Drupal::entityDefinitionUpdateManager()
    ->installEntityType(new ConfigEntityType([
      'id' => 'set_type',
      'label' => new TranslatableMarkup('Set type'),
      'label_collection' => new TranslatableMarkup('Set types'),
      'label_singular' => new TranslatableMarkup('set type'),
      'label_plural' => new TranslatableMarkup('set types'),
      'label_count' => [
        'singular' => '@count set type',
        'plural' => '@count set types',
      ],
      'handlers' => [
        'list_builder' => 'Drupal\your_module\SetTypeListBuilder',
        'form' => [
          'default' => 'Drupal\your_module\Form\SetTypeForm',
          'delete' => 'Drupal\Core\Entity\EntityDeleteForm',
        ],
        'route_provider' => [
          'html' => 'Drupal\Core\Entity\Routing\AdminHtmlRouteProvider',
        ],
      ],
      'admin_permission' => 'administer set type entities',
      'entity_keys' => [
        'id' => 'id',
        'label' => 'name',
      ],
      'links' => [
        'add-form' => '/admin/structure/sets/add',
        'delete-form' => '/admin/structure/sets/manage/{pane_set_type}/delete',
        'reset-form' => '/admin/structure/sets/manage/{pane_set_type}/reset',
        'overview-form' => '/admin/structure/sets/manage/{pane_set_type}/overview',
        'edit-form' => '/admin/structure/sets/manage/{pane_set_type}',
        'collection' => '/admin/structure/sets',
      ],
      'config_export' => [
        'name',
        'id',
        'description',
      ],
    ]));
}

Creating the first bundle

In our first update hook we installed the config entity, now we need to make one for the existing entities, because bundle-less entities use the entity type ID as the bundle, we make sure our new type has the same ID as the entity-type.

/**
 * Adds a new config entity for the default set type.
 */
function your_module_update_8002() {
  $type = SetType::create([
    'id' => 'set',
    'name' => 'Set',
    'description' => 'Provides set panes',
  ]);
  $type->save();
}

Adding the new field definition and updating the entity definition

The documentation for adding a new field definition is again very useful here, so we follow along to install our new field definition. And similarly the documentation for updating an entity type here, so our final update hook looks like this:

/**
 * Updates defintion for set entity.
 */
function your_module_update_8003() {
  $updates = \Drupal::entityDefinitionUpdateManager();
  $definition = BaseFieldDefinition::create('entity_reference')
    ->setLabel('Set type')
    ->setSetting('target_type', 'set_type')
    ->setRequired(TRUE)
    ->setReadOnly(TRUE)
    ->setInitialValue('set')
    ->setDefaultValue('set');
  $updates->installFieldStorageDefinition('type', 'your_module', 'your_module', $definition);
  $type = $updates->getEntityType('your_module');
  $keys = $type->getKeys();
  $keys['bundle'] = 'type';
  $type->set('entity_keys', $keys);
  $type->set('bundle_entity_type', 'pane_set_type');
  $updates->updateEntityType($type);
}

And that's it we're done.

Wrapping up

Kudos to those who created the documentation for this, as well as my colleagues Sam Becker, Jibran Ijaz and Daniel Phin who helped me along the way. Hopefully, you find this post useful if you're ever in the same boat.