Unlike any other solution out there that simply hide the shorts, this one will actually remove shorts from watch history since beginning of time.

By the nature of ever changing YouTube, this solution is likely to break whenever YouTube changes. Check the comments in case someone already posted a fix.

WARNING: I do not take responsibility if something happens to your account, as Google may not like such activity. If you have a billion of shorts watched, removing all may take several hours. So it’s good to take a break once in a while. It is safe to close the page or the browser at any moment and continue later. Also, watch your RAM consumption, loading too much of the watch history may gradually eat all the RAM.

Go to youtube.com/feed/history, then open browser console (usually F12) and put:

(async function() {
  while (window.innerHeight + window.scrollY < document.documentElement.scrollHeight) {
    let days = Array.from(document.querySelectorAll('#contents > .ytd-reel-shelf-renderer'));
    for (let i = 0; i < days.length; ++i) {
      let day = days[i];
      day.scrollIntoView({behavior: 'smooth', block: 'start'});

      let rightArrowButton = day.querySelector('#right-arrow > ytd-button-renderer');
      while (rightArrowButton.checkVisibility()) {
        rightArrowButton.click();
        await new Promise(resolve => setTimeout(resolve, 100));
      }

      let videos = Array.from(day.querySelectorAll('ytd-reel-item-renderer'));
      for (let j = 0; j < videos.length; ++j) {
        console.log(`day ${i + 1}/${days.length} | video ${j + 1}/${videos.length}`);

        while (true) {
          var menuButton = videos[j].querySelector('#button[aria-label="Action menu"]');
          if (!menuButton) {
            console.log('waiting for menu...');
            await new Promise(resolve => setTimeout(resolve, 1000));
          } else {
            break;
          }
        }

        if (!menuButton.checkVisibility()) {
          continue;
        }
        menuButton.click();
        await new Promise(resolve => setTimeout(resolve, 100));

        let removeButton = Array.from(document.querySelectorAll('.style-scope.ytd-menu-service-item-renderer')).
          find(el => el.textContent === 'Remove from watch history');
        if (removeButton.checkVisibility()) {
          removeButton.click();
        }
        await new Promise(resolve => setTimeout(resolve, 100));
      }
      day.remove();
    }

    window.scrollTo(0, document.documentElement.scrollHeight);
    await new Promise(resolve => setTimeout(resolve, 5000));
  }
  console.log('done');
})();

This will go through every visible short on the page, click the three dots menu and then click “Remove from watch history”. After processing all visible shorts, it will scroll the page for more. Once it reaches the end of the history, it will just stop.