Therefore, when an object moves further from the Earth, since it gains gravitational potential energy, will it's observed mass increase?
No, but it is possible to change your analogy in order to make it correct. The thing that's analogous to the nucleus is the system consisting of both the object and the earth, O+E.
If an external source of energy brings the object farther away from the earth, then the total energy of the O+E system is increased, and by $E=mc^2$ this is equivalent to an increase in the mass of the O+E system.
A real-world example of this process, although in reverse, is in the black hole mergers that we observe in gravitational wave events. The black holes transfer a bunch of energy into gravitational waves, which take energy away into the outside world. Typically the system loses about 5-10% of its mass through the merger.
Note that if the system does not exchange energy with the environment, then the system's total energy is conserved, and its mass stays the same.