Dry Ice, a 'sunset' or 'starry night' cyc, and a carpet on a low-ish platform.
The trick with dry ice in this case, would be to get a decent sized tub of warm water, and lower the dry ice in, then use a slow fan placed a decent distance behind the tub to direct the fog onto the stage.
Actually Flying a carpet is difficult and requires specialty equipment and training. Unless your venue has motorised flys and a qualified theatrical aerobatics expert, it cannot be done safely. To fly a carpet and move it across the stage, you would need two motors - for stability, 4 would be better as well as an aerial framework etc, and from where I am sitting, the risk assessment alone would make me want to run the other way.