My story involves a government run program for the paranormal and the main protagonist is a demon. My problem is that I don't want people to think "Hey , you stole that from Hellboy".
This may seem somewhat cliché, but here's what I think: You don't have to worry too much about what makes your story unique because what makes it unique is the fact that you are telling it. No one else is going to tell the story the exact same way you are.
On the other hand, if you are telling the story and just keep thinking, "This is Hellboy," then maybe you don't have the urge to tell a story. Maybe you just want to watch/read/think about Hellboy.
I think as long as there's enough differences in your story compared to Hellboy, you'll be fine. A lot of stories seem similar when boiled down to a simple concept, it's the finer points of character, plot, etc. that makes the difference.
For example, Michael Crichton wrote two stories which were essentially about high-tech, somewhat unethical theme parks going wrong and killing their guests. However, Jurassic Park and Westworld are different enough that it doesn't matter so much (and this is quite an extreme example).
Unless you're incredibly brilliant and creative, any story you write will be similar to other stories in some ways. "Oh, that's a love story, just like Romeo and Juliett." "A story about spies, just like James Bond." Etc.
Fortunately for those of us who like to read fiction, there is a lot of variation possible within these broad categories. If your story matches somebody else's story in a hundred ways, if it sounds like you took somebody else's story and just changed the names of the characters and a few other details here and there, then sure, people will rightly say your story is a rip-off. But having a couple of points in common with someone else's story in the broadest sense ... I wouldn't worry about it.
Think of how many books and movies and TV shows have been written about a brilliant detective who solves a baffling murder mystery. Or about two people who fall in love, then something happens to separate them, then they get back together and live happily ever after. Etc.