Is "a happiness" a valid/commonly used expression?
Because before realizing it, I found myself smiling too, enjoying (a) happiness that came from someone else's heart.
Or maybe happiness isn't countable, so enjoying happiness is the correct form?
Yes, this would be valid. Concepts like happiness that are generally not used with an article (a/the), can have an article if they are qualified.
So here, the part after it ("that came from someone else's heart") makes it a more specific kind of happiness, different to a standard happiness (i.e. that would come from the speaker's own heart).
Qualifying or adding specificity has a few possibilities that add an article, such as with adjectives. So you could also say "I was feeling a deep/temporary/warm happiness because of what happened" - the difference in your example is that the extra descriptive details come after "that". The phrase acts sort of like an adjective, but multiple words are necessary so it's easier to make it a descriptive phrase after "that".
Here is a university grammar book that dives into it a little more:
A University Course in English Grammar By Angela Downing, Philip Locke