How variable does a star have to be, to be a variable star?
There is no lower limit, and as you say, all stars are somewhat variable. 

However catalogues of variable stars exist, and they can record a wide range of levels of variability.  For example, the general catalogue of variable stars lists stars like Alpha Triangulum, with a variability of 0.01 magnitudes.

Ultimately a variable star is a star which has had its variability measured and studied and recorded in a catalogue.