First of all, K2 v2.6 is many, many years old. Upgrade please. And make sure you do the same for Joomla as well.

Secondly, it's most likely a Joomla user group permissions issue at menu and/or category level.

"when I embed the videos into a Joomla article, there is no permissions problem"
>> Perhaps because they were never modified after installation.

"All categories and menus are public or at the most registered"
>> Then the issue may stem on how your actual user groups are made and perhaps importantly, how they are ordered. Additionally, you or someone else may have tampered with K2's global ACL settings, under K2's component settings. If your menus and categories are open for everyone, I'm mostly leaning on the latter.

The easiest way for you to test is to setup a new Joomla site (local or remote, it doesn't matter) and then install only K2. Finally, compare K2's ACL (in K2's component settings) and the default Joomla user groups (and assigned ACL) with your site's K2 ACL and Joomla Groups & ACL settings.

One more thought. If only Super Admins can see content, this means you have to be logged in to view the content. So check if you have some other extension that may control content-viewing. E.g. a plugin that "locks" all K2 item pages or categories automatically to those who are logged. Combined with some obscure ACL setup for users in Joomla, it could explain your issues.

Do the gradual update to K2 v2.10.3 first and then we'll see if anything else is required...

Then it's your Joomla ACL setup, which is expected as K2 does not lock content in the frontend. Only Joomla's ACL can do that.