TL;DR There are few things wrong in how you understand the work-energy theorem:
- the work $W$ does not enter the energy diagram from both sides;
- if you include gravitational potential energy $U$ separately in the energy diagram, then you should not include it again as work $W$;
The work-energy theorem
The work-energy theorem says that the total work done on an object equals change in its kinetic energy
$$\Delta K = K_2 - K_1 = W \qquad \text{or} \qquad \boxed{K_1 + W = K_2}$$
where $W$ is total work done on an object. This means work done by all forces acting on the object! Note that by definition, work is a scalar value that can be either positive or negative.
One thing people usually forget is that the work done by gravitational and elastic (spring) forces equals negative change in the potential energy:
$$W_g = -\Delta U_g \qquad \text{and} \qquad W_e = -\Delta U_e$$
where $U_g = mgy$ is gravitational potential energy and $U_e = \frac{1}{2} k x^2$ is elastic potential energy. Since difference $\Delta$ always means final minus initial value, the work by gravitational and elastic forces is defined as
$$W_g = U_{g,1} - U_{g,2} \qquad \text{and} \qquad W_e = U_{e,1} - U_{e,2}$$
If we use this in the work-energy theorem we get
$$\boxed{K_1 + U_{g,1} + U_{e,1} + W_\text{other} = K_2 + U_{g,2} + U_{e,2}}$$
where $W_\text{other}$ is work done by forces other than gravitational and elastic forces.
Example: A freely-falling ball
As you have correctly identified, the change in kinetic energy can be negative, but the kinetic energy itself cannot. In example of dropping the ball from a height $h$, the energy diagram would be
$$\underbrace{\frac{1}{2} m 0^2}_{K_1} + \underbrace{mgh}_{U_{g,1}} = \underbrace{\frac{1}{2} m v_1^2}_{K_2} + \underbrace{mg0}_{U_{g,2}}$$
or in a general case
$$\frac{1}{2} m v_1^2 + mgy_1 = \frac{1}{2} m v_2^2 + mgy_2$$
which might be more familiar in this form
$$\boxed{v_2^2 = v_1^2 - 2g(y_2 - y_1)}$$
You must be careful what you use for $y_1$ and $y_2$ - subscript 1 denotes the starting point and 2 denotes the ending point.
Work by gravitational force equals negative $\Delta U_g$
As to why work done by gravitational force is negative change of potential energy, we start from the definition of work:
$$W = \vec{F} \cdot \vec{x} \qquad \text{or} \qquad W = \int \vec{F} \cdot d\vec{x}$$
where both force and displacement are vectors, which means they have both magnitude and direction. The work is defined as a scalar product of force and displacement, which means that only portion of force parallel to displacement does work, whereas perpendicular portion does no work. The scalar product finds that portion of work parallel to displacement. If force is constant and displacement is a straight line you can use the (simpler) left-hand side equation, but in all other cases you should use the right-hand side equation.
Let positive $\hat{\jmath}$ axis point upwards (away from Earth's center), then the gravitational force is
$$\vec{F}_g = -mg\hat{\jmath}$$
where $\hat{\jmath}$ is just a unit vector (magnitude equals to one) which defines direction of the force. The work done by gravitational force $\vec{F}_g$ over some distance $\Delta \vec{y}$ is
$$W_g = \vec{F}_g \cdot \Delta \vec{y} = -mg\hat{\jmath} \cdot (y_2 - y_1) \hat{\jmath} = -(mgy_2 - mgy_1) = -\Delta U_g$$
where $\hat{\jmath} \cdot \hat{\jmath} = 1$ is a scalar product between two unit vectors.
