You should and could say any of the following:
"I'm going to the store"
"I need to go to the store"
"I need to go to the store right now"
If you are on your way (walking right now to the store, as you speak) you can say "I'm going to the store right now".
"I'm gonna go the store" is 100% grammatically incorrect, even ignoring the colloquial 'gonna'. If you wanted to use 'gonna' to replace 'going to', you have to add the preposition 'to':
"I'm gonna go TO the store" because you are going TO a place.
A little more detail:
"I'm going to the store" is simply saying just that. There are no specific mentions of time. If you were leaving right now, you can say "I'm going to the store. [the 'right now' is implied] Do you want me to get you anything?" You can also say, "I'm going to the store TODAY/TOMORROW/NEXT WEEK".
"I need to go to the store" is saying that you have a need, a requirement, there is a place you must be. If you wanted to make it even more urgent, you can say:
"I need to go to the store right now" [and that I must hang up]. For example, "I need to go to the toilet." is saying you have an unmet need, that you have to go to the toilet at some point. But if you said "I need to go to the toilet right now.", it means this very moment, is urgent and cannot hold it.