Cancel the cards you don't use. You must do this in writing - simply cutting the cards up is not enough as the accounts will still be active.
The fact that you have recently moved and did not admit it on the application forms rings alarm bells with card companies - you could be anybody. I expect there are a few people in the UK with a name and date of birth similar to yours - anyone of those may have bad credit history, or the address you have moved to may have had bad debtors living there in the recent past.
By not giving your previous address there was no footprint to follow.
Also, store cards are generally provided by credit card companies. Royal Bank of Scotland issue many cards under different 'brandings' . If you already have several cards with them, you may be at the maximum credit limit for that company.