Clock that changes document background color
Questions

I suspect that this code is messy.

It doesn't really look very messy... One great aspect is that the DOM references are cached.

Is there a way the following JS code be made efficient?

I'm not sure it needs to be much more efficient. The code looks similar to many examples one can find searching the internet for a clock in JavaScript. If memory was an issue and you really wanted, perhaps you could create only one date object and merely update that date object with the updated hour, minute and seconds values but you would need to do the bookkeeping manually, which might end up being less efficient.
Suggestions
global variables
The variables created using var are technically global variables, since they are not contained in a function. For a small script like this it likely won't make a difference, but in a larger application that can lead to namespace collisions. It would be wise to wrap the code in a function (perhaps in an IIFE) and use const/let instead of var to keep the scope limited.
Use Date method to get formatted time
It could be simplified by using the Date method toLocaleTimeString() (or alternatively Intl.DateTimeFormat()). See the example below for a demonstration of this.
Edit: I realize after posting it that the 24-hour format was still the default for the hours so I had to add hour12 to the options and an extra call to .replace() to remove the am/pm. Also that doesn't apparently support the 2-digit format well so it also has to additionally add the leading 0 if necessary. Apparently this code suffers from this issue.


(function() { //IIFE
  const clock = document.getElementById('clockElement');
  const color = document.getElementById('hex-color');
  const options = {
    hour: "2-digit",
    minute: "2-digit",
    second: "2-digit",
    hour12: true
  };

  function hexclock() {
    const time = new Date();
    //use preferred locale accordingly
    let clockString = time.toLocaleTimeString('en-GB', options).replace(/[a-z\s]/g, '');
    //add missing 0 - hour12 doesn't work ideally for this scenario
    clockString.length &lt; 8 &amp;&amp; (clockString = '0' + clockString);
    const hexColorString = '#' + clockString.replace(/:/g, "");

    clock.textContent = clockString;
    color.textContent = hexColorString;

    document.body.style.backgroundColor = hexColorString;
  }

  setInterval(hexclock, 1000);
  setTimeout(function() {
    console.log('window.clock (global variable)? :', window.clock !== undefined);
  }, 1100);
})(); //end IIFE
body {
  marin-top: 20px;
  text-align: center;
  color: white;
}

#clock {
  font-weight: 300;
  font-size: 60px;
}
&lt;h1 id="clockElement"&gt;00 : 00 : 00&lt;/h1&gt;
&lt;p id="hex-color"&gt;#000000&lt;/p&gt;