First, have your looked in Nørresundby Kirkebøger (churchbooks) for their marriage (Viede)? Was your father a first child? Or were there older children? That has a bearing on your timeline. (Consider looking for a marriage date up to and including 1884.) Looking in Nørresundby would be the obvious first step. Unfortunately, I haven't been able to get into Statens Arkiver https://www2.sa.dk/ for the last couple of weeks or I would look for you.
I use the Family History Library catalog search as my gazetteer and I see only one Nørresundby in Aalborg amt (county). I determined it was in Kaer herred (district) by searching a map of Aalborg jurisdictions at http://www.danishfamilysearch.dk/amt2. However, when I search for Hellum, I see that it is both a herred in Aalborg amt and a sogn (parish) in Hjørring amt, the county just north of Aalborg amt. I suspect you mean Hellum sogn. If so, it is in Dronninglund herred, the herred nextto Aalborg boundaries. See the map of Hjørring jurisdictions: http://www.danishfamilysearch.dk/amt9. If I'm being tedious about this, it's because you must have the right place to find anything specific and also that different records are held at different levels of jurisdiction.
Typically in a settled society, the marriage takes place in the bride's church. Have you looked for your grandmother's family in Nørresundby? If you cannot find them there, you might be able to determine when your grandparents arrived in Nørresundby. I see that the Family History Library has Til and Afgangslister (arrival and departure lists) for Nørresundby only up until 1875. That might be useful for an earlier arrival.
If your grandfather came from Hellum sogn in Hjørring, you can search online both at Statens Arkiver and at FamilySearch https://familysearch.org/search/collection/2078555 by selecting Browse and drilling down by amt, herred, to the Hellum sogn and a listing of available records. You are in luck if your father was born no earlier than 1855. You can look for birth records (Fødte) in Volume 13 (1855-1875). Otherwise, there appears to be a gap in this record set that I have verified exists also at Danish Family Search www.danishfamilysearch.dk.
Be very careful in identifying persons by name. If you have your grandfather's birth date or the names of his parents, you can ensure that you have the right person. Remember that the records are in Scandinavian Gothic script. For help, see Denmark Handwriting https://familysearch.org/learn/wiki/en/Denmark_Handwriting. For words you'll encounter, see Genealogical Words in Danish Research https://familysearch.org/learn/wiki/en/Category:Genealogical_Words_in_Danish_Research
For triangulation, you should look for your grandparents or their families in the 1880 census. The Folketaelling (census) for Hjørring amt is available online -- when it works -- at Statens Arkiver. https://www2.sa.dk. You must know the herred as well as the sogn. Use the same procedure for Aalborg amt.