Try disabling the "Ignore multiple sources" option either in JoomSEF's Advanced configuration or only for the K2 extension in Manage Extensions -> K2 -> Common tab. Make sure to delete the already created SEF URLs and clear Joomla and JoomSEF caches after making changes in configuration.

Now we get the correct SEF url but also error:

404 - Category not found

You may not be able to visit this page because of:

an out-of-date bookmark/favourite
a search engine that has an out-of-date listing for this site
a mistyped address
you have no access to this page
The requested resource was not found.
An error has occurred while processing your request.

Please try one of the following pages:

What do the Real URLs for your SEF URLs look like (please post examples from Manage SEF URLs page)? Do you have only one category or multiple categories selected for each menu item?