The Lord of the Rings trilogy, with principal photography taking place in 1999 and 2000, was mostly shot on 35mm film which was then digitised for editing, CG overlay and color correction. It also would have been distributed to cinemas that were still running film projectors - the changeover to digital wasn't until around 2010.
35mm film is essentially 7680p, or 11K (possibly even double that.
As such - the quality of the movie imagery printed for cinema then would easily outstrip DVD and Blu-Ray, and will still outstrip the new 4K offering. By remastering from the original digitised assets, the studio can easily produce a true 4K release. Incidentally, this is why many older movies that are remastered for Blu-Ray already look superior to DVDs, because remastering means the studio are creating the Blu-Ray master from original film to produce the 1080p image. Many DVDs (not all), on the other hand, were produced from VHS masters, so even though DVD allows for 720p, some movies won't look better than the original VHS release.
The Hobbit was shot in 5K (3D), so there's still some room for a 4K version to be released.
Most digital movies are shot using 8K cameras (starting back with Star Wars: Attack of the Clones or even earlier). Most cinemas are now projecting 2K or 4K - with some even projecting at higher resolutions already.
