Does energy have a sign?

To be honest, signs don't exist. Energies don't exist. They are merely methods or models or descriptions invented for us to describe forces, tendencies, absorption of radiation, impacts, vibrational motions, directions etc. So, does negative energy exist? We can just invent it, like you just described for the potential energy, so yes.

• In some situations a sign describes nothing but the size of values (when it doesn't matter where the origin is, such as with potential energies with arbitrarily chosen reference points),
• in other situations the sign describes the mathematical act of adding or subtracting (like heat absorbed or expelled),
• while in yet other situations signs describe directions on a predefined axis (your axis defines forward, so a speed moving you backwards is negative).
• Etc.

A sign is a mathematical invention that means different things in different contexts, depending on what we need to do.

conveying that a negative amount of work is done

A "negative amount of work" belongs to the 2nd bullet point above. Work being negative just means that energy is leaving (mathematically subtracted) the object. The negative sign is here nothing more than mathematical.

The question about "existence" is philosophical one, not a physics one. Some people would argue that you can't be sure about the existence of anything, including yourself.

Physics is concerned with creating mathematical models that can make predictions about the outcome of a experiment or situation. All physical models have limited applicability, i.e. the predictions are only accurate if certain conditions are met. So far there aren't any models that are truly universal and applicable in every possible situation.

Negative, or positive, energy are just that: concepts that are useful to make quantitative predictions in certain situations (but not in others).

For example, negative energy is a useful concept is energy is moving around inside a system. If it's moving one way you call it "positive" , if it's moving the other way it's negative.

Of course it is very important in some calculations if the energy change in some system is positive or negative. If you are building a power plant, rather try to get a positive amount of energy out!

But that's only differences in energy. The point of energy zero is defined arbitrarily and you can always redefine it, so that the absolute sign of $E$ is unimportant.