Where does the heat from friction come from?

You do work on the object, and the object does work on the surface (the negative work in your description). So it's true that the net work on the object is 0, but you transfer your energy through it to the surface. And as you put energy into the system but the kinetic and potential energies stay the same, the energy turns to heat.

The "work" done by friction based on Newton's laws of motion does not account for the change in internal energy of the object (change in temperature). The work based on the laws of motion is for motion of the center of mass of the object and are correct for motion of the center of mass, even if changes in internal energy occur, but these laws do not provide any evaluation of changes in internal energy, heat transfer, of motions of particles in the object. Based on the first law of thermodynamics for this case the total "work" on the object = change in internal energy of the object. The first law work is different from the work based on the laws of motion. In the literature, some denote the work based on the laws of motion as pseudo-work and use work for the thermodynamic concept: energy that crosses a boundary without mass transfer due to any driving difference except temperature. See any basic thermodynamics text.