Skype is no longer updated or available for Windows 7 phones but should be fine on your 8.1 phone.
From what I can tell it is eBay that has pulled the plug on the Windows phone app, not Nokia or Microsoft.
You have no redress from Tesco - they are not responsible for this. It is the same as those who have bought expensive smart tvs and later find that apps and services are no longer supported; and those who had very expensive Blackberry phones only to find apps ceased to be supported.
In the fast changing world of technology it is inevitable that app developers will concentrate on the most popular formats and app developers will fall out with phone providers.
You have the choice of continuing to use the phone for the duration of the contract or paying extra to upgrade. You should still be able to access eBay through the browser.