Menu tree from taxonomy terms and nodes which belong to them
That's probably an opinion-based thing and actually also a too broad question. But here's what I'd do:


Programmatically create a new block.
Provide a hook_theme and your own template to later render the output the way you want.
Follow one answer from How to get all node entities tagged with a specific term? to get the data you need.
In the block's build() function pass the data to your custom template and build the markup you need.
Optional: Improve performance by either storing the data from step 3. in some Drupal variable that can be purged from some admin settings form button click. Or add some custom cache tags that get invalidated as soon as taxonomy or node CRUD operations take place.




You probably can achieve what you want with some Views voodoo, and maybe should try that first, depending on your programming skills.