I haven't found "fancy paper" in a dictionary. I could only guess by using an images search and reading sentences containing the word. So I am not sure if "fancy paper" can be used as an exact synonym for the terms "gift wrap paper" and "wrapping paper". Besides that, does "fancy paper" have any additional meanings?
I've never heard of wrapping paper referred to as "fancy paper". Searching on Staples.com, some of the results are, indeed wrapping paper, but some of the results are just special or artistic paper (for writing on), so I wouldn't count on others knowing what you mean if you try to use them as synonyms.
Gift wrap paper or wrapping paper isn't called "fancy paper", but you could say something like this and no one would bat an eye:
Before we give him this plaque, we should wrap it up in some fancy paper.
If you went into a stationery store and asked for fancy paper, they wouldn't know what you had in mind and would probably ask whether you wanted writing paper or crafts paper or wrapping paper.