First : 

Import the attributes and their values

Do not forget the "dynamic" creation mode

Second : 

Import the attributes and value possible on the product template

For now, no product variant have been created yet.

Third : 

Create a new menu linked to existing model "product.template.attribute.value"

From this new menu, you can export all the value of the attributes and their id

Finally : 

Create a file for the import

First column : id to define yourself

Second column : id of the product template linked to this combination of value

Third column : "product_template_attribute_value_ids/id" where you put the combination of value using the id of the values with a coma and no space between them.

This means you will use one line of your file per possible combination and you will have multiple lines of combination linked to the same product template.