Clearing local tasks cache
First of all it might be that you found a bug in core (a caching issue), so it would be great if you could report it to the Drupal core issue queue as well. There is extensive test coverage for local tasks, but it might be that there is none for adding new entities and that those in core just work due to side effects.

To solve your immediate issue I would try to invalidate just the render cache of the local task blocks.

To find out the cacheability metadata of the local tasks the easiest is to install the renderviz module:

https://www.drupal.org/project/renderviz/

and apply the patch from this comment

https://www.drupal.org/node/2640280#comment-11286381

Once you have that installed and you go to the page with your local tasks, you will see a list in the JS console of all cache tags present.

For the bartik theme you will find (e.g. tested with core search pages, which have similar code to yours):

config:block.block.bartik_local_tasks

If you put into the console:



  renderviz('tags', 'config:block.block.bartik_local_tasks');


Then you will see that indeed the primary local tasks will be highlighted.

So in your hook_entity_insert() / hook_entity_update(), you can just do:



 Drupal\Core\Cache\Cache::invalidateTags('config:block.block.bartik_local_tasks');


And that will invalidate just the local tasks block and solve your issue for now.

What should have happened however is that the local tasks block should show both the cache tags for the list [entity-type] and the entities itself. (like a normal listing of entities)

e.g. if you want to change the title of any of your entities, core should based on the deriver update the local tasks block.

And that we don't do that is likely a core bug in regards to cacheability metadata, so please file it. Unless I miss something and there is some special code that makes this work for core's derivers out-of-the box.

Edit:

We correctly add the cache tags of the config entities, however there is no 'list' cache tag, which means that whenever you add or delete a config entity the local tasks don't get invalidated.

As you have a plugin, you can likely just add your own custom cache tag to the plugin definition.

e.g.

$base_plugin_definition['cache_tags'][] = 'local-tasks-my-entity-type-list-cache-tag';


Then just invalidate that list cache tag in your insert / update.

But that definitely is also an issue in Drupal core as I can reproduce it purely with core search pages.

I missed in your question at first that caches fail to get invalidated only when adding or deleting new entities.

That however was the key clue.

Edit 2:

Core should be invalidating list cache tags automatically, so the easiest is to just use the pre-defined list cache tags.

This is the diff that fixes the bug for me in core:

diff --git a/core/modules/search/src/Plugin/Derivative/SearchLocalTask.php b/core/modules/search/src/Plugin/Derivative/SearchLocal
--- a/core/modules/search/src/Plugin/Derivative/SearchLocalTask.php
+++ b/core/modules/search/src/Plugin/Derivative/SearchLocalTask.php
@@ -52,7 +52,9 @@ public function getDerivativeDefinitions($base_plugin_definition) {
           'route_name' =&gt; 'search.view_' . $entity_id,
           'base_route' =&gt; 'search.plugins:' . $default,
           'weight' =&gt; $entity-&gt;getWeight(),
 -        );
 +        ) + $base_plugin_definition;
 +
 +        $this-&gt;derivatives[$entity_id] += ['cache_tags' =&gt; []];
 +        $this-&gt;derivatives[$entity_id]['cache_tags'] += $entity-&gt;getEntityType()-&gt;getListCacheTags();
       }
     }
     return $this-&gt;derivatives;


That fixes the bug for me for core search pages.