Hi,
When you already have variants in your product and you add new characteristics, hikashop doesn't know what to do (imagine that you changed some data in the variants...if hikashop delete them in order to recreate all the variants, you're screwed) so it doesn't create the variants automatically.
If you want it to recreate all the variants automatically, you need to delete all the variants of your product first. Then, go back to the product, delete the characteristics and save the product. Then, add the characteristics again and save the product and all the variants will be recreated automatically.