What do you get if you temporary unproxy (DNS-only) that DNS record?
Does it work then?
Have you tried to use “Purge Everything” option from the Cloudflare dashboard → Caching → Configuration?
I wonder if the wildcard * record could cause and be the issue, just guessing
And the VPS vhost file of that sub-domain store is configured to return the corelated content for store.domain.com?
May I ask if you are using some Page Rules for it or?
May I ask have you tried using a different Web browser, or tried clearing your Web browser cache?
How about using a Private window (Incognito mode) or a VPN connection if possible?
Is it the same behaviour on your mobile phone (4G LTE, mobile data, cellular)?