I have tried removing old devices at iCloud.com and at the iTunes "Manage Devices" section. I still see the old devices appearing in the Apple Store app. As a side effect, High Sierra also shows two Apple Watches for automatic unlocking. Any tips on removing the old devices?