I found this article in the Google Support, Remove devices & add device nicknames. Apparently you can HIDE old devices from showing up in the Google Play Store menus. I cannot find anything on actually deregistering an old device, but this might unofficially do that.

I checked Amazon's app store and apparently I had already deregistered my old phone from there.