We measure the proper motion of the pulsar PSR J1745-2900 relative to the Galactic Center massive black hole, Sgr A*, using the Very Long Baseline Array (VLBA). The pulsar has a transverse velocity of 236 +/- 11 km s^-1 at position angle 22 +/- 2 deg East of North at a projected separation of 0.097 pc from Sgr A*. Given the unknown radial velocity, this transverse velocity measurement does not conclusively prove that the pulsar is bound to Sgr A*; however, the probability of chance alignment is very small. We do show that the velocity and position is consistent with a bound orbit originating in the clockwise disk of massive stars orbiting Sgr A* and a natal velocity kick of <~ 500 km s^-1. An origin among the isotropic stellar cluster is possible but less probable. If the pulsar remains radio-bright, multi-year astrometry of PSR J1745-2900 can detect its acceleration and determine the full three-dimensional orbit. We also demonstrate that PSR J1745-2900 exhibits the same angular broadening as Sgr A* over a wavelength range of 3.6 cm to 0.7 cm, further confirming that the two sources share the same interstellar scattering properties. Finally, we place the first limits on the presence of a wavelength-dependent shift in the position of Sgr A*, i.e., the core shift, one of the expected properties of optically-thick jet emission. Our results for PSR J1745-2900 support the hypothesis that Galactic Center pulsars will originate from the stellar disk and deepens the mystery regarding the small number of detected Galactic Center pulsars.