Creating non-clustered index on large table fills transaction logs
As far as I know the fact that the underlying table is a columnstore index isn't too relevant here. The linked documentation that you included in the question already gives you the standard fixes for your problem. Below is a list of possible fixes rated in 


Increase your log file size. This will help you in the future if you ever need to drop and recreate the index for some reason.
Set the SORT_IN_TEMPDB option to ON. I didn't know this, but that option can help in cases when you have enough free space in tempdb.
Build the index with page compression. This can reduce the amount of data written to the transaction log, but that varchar(4000) column could cause issues.
Create a copy of the table's structure with the indexes that you need and insert data into it in batches. This can be difficult to pull off in production and will overall be inefficient but you can split up your index build into separate transactions this way. If something goes wrong just drop the temporary copy of the table that you made.
If the table is partitioned, you might be able to use partition switching to build the nonclustered index one partition at a time.
Temporarily change your recovery model to bulk-logged. This can cause all sorts of issues so make sure that you fully understand all of the ramifications of doing this.