In order to have SEF URLs, content from components has to be mapped to at least one menu item.

In this case, SPPB may be mapped to a menu item, but K2 isn't. SPPB just fetches K2 content directly, either by calling one of K2's modules or by direct SQL queries. SPPB acts as a shell, it doesn't hold/resolve the actual content.

To address your issue, you can create a menu in Joomla to map your K2 categories and in there create on or more menu items pointing to K2. This menu does not have to be public on the site. However it will allow you to have better looking URLs for your K2 content.

Keep in mind that what you face here is not K2 specific. The same would apply for any other component that is being retrieved inside SPPB.

Yes and yes. :)

Nest the menu items. Use the one for SPPB as the top level menu item and then add any/all K2 menu items as children to the SPPB menu item. This way URLs won't clash.

BTW, this is not a K2 or SPPB limitation, it's how menu item aliases work in Joomla.