1) To create categories go to Products > Categories > create parent category Men for example and subcategories for the men, then pager category kids and subcategories for the kids etc. In the product categories widget settings, you can choose “Only show children of the current category” http://prntscr.com/lkdm8o and then when you’ll be on the men category you’ll only subcategories for the men category.
2) Create different attributes with terms for every global category like men colors, kids colors etc http://prntscr.com/lkdph6 (Products > Attributes) then when you create product choose the appropriate attribute in variation options http://prntscr.com/lkdpyo After that you’ll be able to add attribute filters into shop sidebar http://prntscr.com/lkdqil but they will be visible depending on product category that includes products with these attributes.
3) If you don’t want to mix brands then I would suggest you to use attributes instead of our brand option. Create Men brands attribute with brands as attribute terms and use it for the products but don’t check use for the variations http://prntscr.com/lkds8x
You can add Product categories widget in “Shop sidebar” or “Shop filter” (Appearance > Widgets) + Enable Accordion for the product categories widget in Theme Options > Shop elements > Categories. Settings for the sidebar and filters you can find in Theme Options > Shop > Shop page Layout.