I went to Michael's for all the stuff I needed to make the bottle wax myself, but, yeah, candle wax won't work.
You can buy the bottle wax from your lhbs or online and it's really easy that way, but it tends to be expensive and doesn't leave much room for customization or experimentation.
The recipe I used was 22 hot glue sticks, 10 crayons, 1/8lb paraffin wax, and purple glitter. With this recipe, they are plasticy--almost as much as a Maker's Mark bottle--but they crack open easily with a regular bottle opener.
The thread with the bottle wax experiment and results of those who used the evolving recipe is here:
https://www.homebrewtalk.com/f35/hot-glue-bottle-wax-experiment-127485/