The firm evidence we have is Martin Luther adding candles to a tree (Wikipedia source). That same article goes over two probable origins for the tree:

• Paradise trees, as your linked YT video explains
• Vikings and Saxons worshipped trees, and that custom often survived conversion to Christianity

This is particularly interesting:

Tree worship was common among the pagan Europeans and survived their conversion to Christianity in the Scandinavian customs of decorating the house and barn with evergreens at the New Year to scare away the devil and of setting up a tree for the birds during Christmas time."

…

The Vikings and Saxons worshiped trees. The story of Saint Boniface cutting down Donar’s Oak illustrates the pagan practices in 8th century among the Germans. A later folk version of the story adds the detail that an evergreen tree grew in place of the felled oak, telling them about how its triangular shape reminds humanity of the Trinity and how it points to heaven.

This article puts the origin of the Paradise Tree around the 12th century, whereas the above quotes point to earlier traditions.

I think they borrowed from each other. I think pagan converts were adorning their houses with evergreen boughs long before the Paradise Plays and feast of Adam and Eve around the 12th century.

Here’s what could be a rough sequence of events:

1. Pagans worship trees and adorn their houses with evergreen boughs
2. Catholic missionaries spread Christianity across Europe
3. Early Christian converts retain many of their ccustoms while starting to incorporate Christian customs
4. Catholic church seeks to replace pagan observances with Christian ones (e.g. Christmas being on Dec 25 was likely to replace pagan celebrations at the time)
5. A mix of 3 & 4 results in evergreen trees being used as Paradise Trees in the 12th century, which evolves into Christmas trees by the 16th century

That’s why I say the custom came from paganism. But obviously history is much more complicated.