What is the origin of using 'x' to mean 'with', and how has it spread?

The use of "X" is simply shorthand

OED

X (n.)

I. The letter, its sound or shape;

1 b. The letter considered with regard to its shape: chiefly attributive and in other combinations. Hence identified with a cross. X's and O's: the game of noughts and crosses. X chair, a chair in which the underframe resembles the letter X in shape;

1545 Bibliotheca Eliotæ Decussis..is also a fourme in any thynge representynge the letter X, whiche parted in the myddell maketh an other figure called Quincunx, V.

1861 H. Hagen Synopsis Neuroptera N. Amer. 213 An x-shaped spot.

1893 F. C. Selous Trav. S.-E. Afr. 402 I will write your name..on the paper..and you must make an ‘x’ behind your name.

1976 Country Life 27 May (Suppl.) 486/1 Late 18th century wheel-back armchairs with saddle seats and X-frame legs.

Thus Viburnum × burkwoodii, = A cross between Viburnum and burkwoodii.

Where cross (OED) =

28.a. An intermixture of breeds or races in the production of an animal; an instance of cross-fertilization in plants.

1766 T. Pennant Brit. Zool. i. 8 Improved by a cross with the foreign kind.

b. An animal or plant, or a breed or race, due to crossing.

1761 Philos. Trans. 1760 (Royal Soc.) 51 834 The bird..is an accidental cross, as we sportsmen term it, between a pheasant and turkey.