eBay store categories are located on the Sell on eBay tab of your products. To access this tab, click on the title of your product and then click on the Sell on eBay tab on the left menu.
To setup your eBay store categories for your products, you must Enable product level eBay settings. Your eBay store categories can be re-synched with your eBay store by clicking on the green double arrow icon (Item 1).
More information on the Sell on eBay product tab can be found here