The pairing has a documented origin, which is unusual and worth stating plainly because it is often presented as immemorial.
Robert Graves published The White Goddess in 1948, arguing that all true poetry derives from a single ancient theme: a goddess and a sacred king who is displaced each year by his rival and successor, the tanist, who is his own other half. Graves worked that theme through a tree alphabet he reconstructed from Irish and Welsh material, assigning trees to parts of the year, and the oak and the holly fall on the two halves either side of the solstices. From that arrangement the two kings emerge as the rulers of the waxing and waning year who kill each other in turn.
Graves was explicit that the book was an argument made as a poet. Celticists have not accepted the tree alphabet as he reconstructed it, nor the chronology he built on it, and the specific figures of an Oak King and a Holly King are not attested under those names in any medieval Irish or Welsh source.
They entered practice quickly. Wiccan and wider modern Pagan groups forming in Britain in the 1950s and 1960s took the seasonal framework up as the eightfold Wheel of the Year settled into its present shape, and the two kings supplied the solstices with a narrative that the equinoxes and cross quarter days already had in other forms. Within a generation the pairing was general across the modern Pagan movement, and it remains so.