On every page, it say's "Product Categories." Where do I edit this? I looked in the menu, modules, k2 items, k2 categories, and could not find where to edit this.
Now I understand why You have problem with this. I've searched for settings about this title in K2 category and in menu item, but this looks to be a static value. I can see this text in /languages/en-GB/en-GB.com_k2.ini lang file. You can remove it there or add this part of code to override.css (make sure override is enabled in template settings):