Can I change iCloud ID
They don't have to be the same. Sign out of iCloud in Settings and set up the new Apple ID. Then, if that Apple ID's also been applied to the stores, go to one of them, sign out, and sign back in with your store Apple ID.

Source: My own experience - my iPod Touch works fine with my own Apple ID for iCloud and my family's Apple ID for the stores.