what could be going on here?
He may benefit from perspective-taking, respecting the others' view, and developing Theory of Mind.

has a hard time following social cues and gets alienated.
Direct teaching can help with this. Books such as You are a Social Detective.

The other kids seem to be able to tell he is "different." Sometimes he wants to play but ends up hitting another child just for the hell of it... The other kids run away and don't want to play with him and he wonders why... sad for him that he was bullied ...
Although you say he was bullied, details in your post seem to indicate that he was the aggressor, the bully, and the other children did the best they could at that young age to maintain healthy boundaries.

...or spitting at them
Bodily fluids present a biohazard. Your son's actions may be considered a serious form of assault.

When asked why he keeps doing this his response "I just like making other people feel bad..." should we be concerned about this or could it be part of being gifted in some way?
This is a red flag. Be concerned.

It took awhile to find but there is this old thread with an article linked in the original post which discusses kiddos without conscience, empathy, or compassion. Interestingly they exhibited strength in manipulation, what some may call leadership, and also organized "teamwork" in their scary, dangerous, antisocial behavior. Fortunately the article contained hope in the sentence "Physiology isnít destiny.Ē

These children may be the opposite of those who exhibit a common trait in gifted children, often listed amongst identifying characteristics, which is alternately described as "advanced moral reasoning", "well developed sense of justice", "moral sensitivity", "advanced ability to think about such abstract ideas as justice and fairness", "empathy", "compassion". Links to lists of gifted characteristics include several articles on the Davidson Database here and here, SENG (Silverman), SENG (Lovecky).