Se puede resolver con `replace` de un modo relativamente sencillo, usando una expresión regular que ignore mayúsculas y capture el grupo encontrado para añadirle la etiqueta deseada.

Incluso simplificando el código he conseguido que al borrar caracteres se amplíe la búsqueda de nuevo, a veces menos es más :)


<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

    const input = document.getElementById("searchDocs");
    input.addEventListener("input", () => {
      const value = input.value;
      const sections = document.querySelectorAll(".docSection");
      sections.forEach(el => {
        el.innerHTML = el.innerText;
        el.removeAttribute("style");
      });
      if (value.trim() !== "") {
        sections.forEach(el => {
          if (!el.innerText.toLowerCase().includes(value.toLowerCase())) {
            el.style.display = "none";
          } else {
            el.innerHTML = el.innerText.replace(new RegExp(`(${value})`,"i"), "<strong>$1</strong>");
          }
        });
      }
    });

<!-- language: lang-html -->

    <h1>Search</h1>
    <p><hr/></p>
    <p class="docSection">Java</p>
    <p class="docSection">Python</p>
    <p class="docSection">C</p>
    <p class="docSection">CSharp</p>
    <p class="docSection">PHP</p>
    <p class="docSection">HTML</p>
    <p><hr/></p>
    <p><input id="searchDocs" placeholder="Escribe para buscar" /></p>

<!-- end snippet -->


 **Explico un poco el *truco***:

El usuario escribe por ejemplo "p", así que lo queremos es buscar la primera coincidencia, sin importar mayúsculas o minúsculas, y ponerla en negrita. Así que construimos una regex que *capture* esa "p" en un grupo:

    let regex = /(p)/i; // i de "ignore case", ignorar si es mayúsculas

Pero como esa p es una parte variable, usamos el constructor equivalente:

    const value = "p";
    const regex = new Regexp("(" + value + ")","i");

Los paréntesis capturan lo encontrado en un grupo, que luego podemos referenciar como *grupo 1* o, en la clásica notación de regex, $1:

    innerText.replace(regex, "<strong>$1</strong>");