Would it be feasible in any rocket engine (liquid or solid) intended for flight above the atmosphere to add one of the following elements: barium, lithium, sodium, copper, or calcium to create different colors in the exhaust plume, or would those elements render all engines not flight worthy?
Sure, it's entirely possible. Not unusual in model rocketry (where style points can count for something), for example:
There are several ways to do this.
Night time launch close to sunset or sunrise so that the rocket quickly reaches an altitude where it is illuminated by the Sun. The bright sunlight can then cause atoms and molecules in the plume to fluoresce, seen against a dark sky.
Keep in mind that there can be a huge amount of yellow/white blackbody radiation from soot particles in RP-1/LOX and SRB exhaust, and that could overwhelm your color effect. For more on that see What is the cause of the blue light from LH2/LOX rocket engines?
Photons in the ultraviolet component of sunlight in space are more efficient at inducing fluorescence than the UV that makes to the ground.
Some materials fluoresce nicely. Diatomic carbon or $C_2$ is famous for making comets appear green, but copper compounds are pretty common for blues and greens as well.
From this answer to In the recent Con-Ed transformer “fire”, what exactly produced the color of the huge blue glow over New York City?:
below: "C/2014 Q2 (Lovejoy) is a long-period comet discovered on 17 August 2014 by Terry Lovejoy. " Source
Below is borrowed from Why is one of these two concurrent fuel-dump spirals blue?:
above: From here
Copper sulphate solution can be stored as a liquid and easily pumped and sprayed/atomized into the plume where it would quickly disperse. However the plume would have to be hot enough to dissociate the copper atoms and excite them sufficiently to fluoresce:
Images from CNN's A transformer explosion turned the New York City skyline blue
Night time launch close to sunset or sunrise so that the rocket quickly reaches an altitude where it is illuminated by the Sun. The bright sunlight can then reflect off of material in the plume, seen against a dark sky.
Very thin, light weight, combination of plastic and other dielectric films dumped overboard at a controlled rate.
Source: New York Times What Is Glitter? A strange journey to the glitter factory. click for full size
"Colored smoke is a kind of smoke created by an aerosol of small particles of a suitable pigment or dye."