Gravitational potential does not require a change in position, it requires a hypothetical change in position. Wikipedia defines gravitational potential as the energy "that would be needed to move an object to that location from a fixed reference location" (emphasis mine). Two masses always have gravitational potential with respect to each other. It's possible to calculate the potential energy of a mass with respect to some point even in total absence of any information of how it got there, whether it was positioned through normal methods, or was magically put into place by some physics-defying method. A mass in a gravitational field will fall when released - to suggest that a mass spontaneously appearing in a gravitational field might not have potential energy implies that the mass can defy gravity. Assuming the only thing "special" about the mass is its spontaneous appearance, it will be affected by gravity just like every other bit of matter.
Furthermore, gravitational energy is always computed with respect to some particular point. It's not mathematically possible for a mass to have zero potential energy with respect to all points, as that implies there is zero potential energy difference between any of those points, which is clearly not the case. A mass cannot have 0 PE with respect to the earth and 0 PE with respect to the sun, as that implies there is 0 PE between the earth and the sun, which is obviously untrue. Note that we can calculate the earth's PE with respect to the sun regardless of whether the earth was positioned by hard physics, or placed by a divine being. Potential energy describes a state, not the process that led to it. Once the object magically appears, the state is indistinguishable from one where the object was placed normally. The object is there, so it has potential energy - how it got there is irrelevant.
Of course, a mass "spontaneously appearing" may be physics-defying in itself, but if we take that at face value and assume all other physics operate as usual, the mass must have potential energy.