Create a menu(e.g. sidebar menu) which contains category names. Bind each menu item to one category. Place that menu in a module and choose to display that module on all(or some specified) pages. Don't forget to publish what you create.
To show all items from all categories, bind a main menu item to K2 categories by choosing menu item type. On menu item's options tab select all categories. OR if all of them have same parent category(which may be abstract, with no items), select that category and set "Fetch items from children categories" to "Yes".
This way you will have all items from all categories shown when selected main menu item, and have them filtered by category when selected sidebar's menu item.
Hope it helps
Zura