If cells regularly renew, why do we have scars?
Scar tissue formation is part of the normal healing process in which fibrous material braces and pulls the wound together, in other organisms (and young mammals) this process is mild and just serves to temporarily reinforce the damaged tissue as new cells migrate in to begin replacing the missing tissue, sometimes to the point of replacing missing limbs in lizards and amphibians. However in adult mammals and birds the process of fibrous tissue is far more exaggerated, creating longer lasting or even permanent scars, Here the wound keeps filling in with more and more fibrous tissue instead of moving on to regenerating what was there originally. This dense fibrous tissue often prevents new cells from easily migrate into the tissue, essentially stalling the healing process. It seals the wound much faster than the more mild deposition of other animals but can often prevents replacement of the fibrous tissue which would otherwise happen as the missing tissues is regenerated. This mass of fibrous tissue is what we call a Hypertrophic scar. this is why scars can also fade, as cells often can migrate in and slowly replace the the matrix but this is severely limited by the dense packing.

Note there is a second rarer form of scar tissue that can form, called keloid scarring. This form of scar spreads beyond the original wound area and seems to be caused by some form of runaway extracellular matrix deposition. It should also be noted adult mammals sometimes do regenerate decent portions of tissue, albeit not well, possibly because some of the controlling cellular signalling machinery has be lost or reappropriated. All the factors that affect this are not understood and are a main focus researched. We do know it varies quite a bit from tissue to tissue and is not terribly consistent. 

It is believed that mammals and birds develop this stronger matrix deposition which leads to permanent scar tissue becasue healing fast is more important for them than healing completely since their metabolism runs so much higher. They can't wait around for it to heal they need to get moving as soon as possible or risk starvation,additionally a stable body temp makes for a more inviting environment for bacteria so sealing the wound is paramount. Thus sealing and mechanically reinforcing the wound is more important than regeneration. As you can imagine the worse the injury the more important it is to plug it fast which is why minor injuries are less likely to scar. This is also why lizards and amphibians end up with less permanent scars they can take the time to better regenerate the tissue. Of course this is difficult hypothesis to test, however there has been some success in getting mammalian tissue to regenerate more by removing scar tissue as it forms or just preventing collagen production. 

Evolution is one lang story of "good enough" and scar tissue is good enough functionally that the speed at which it can seal a wound favors it over slower regeneration.