Multi-column and single-column index on the same column
Get rid of OR

(s.deleted = 0 OR s.deleted IS NULL)


Make up your mind.  Either use 0 (and make it NOT NULL) or use NULL.  It is probably better to have 

TINYINT UNSIGNED NOT NULL DEFAULT '0'


Until you get rid of the OR, an index including deleted is not useful.

Composite index

After that, INDEX(deleted, store_id), in either order, becomes optimal.

As a rule, INDEX(a) is unnecessary if you also have INDEX(a,b).

Even better is

INDEX(deleted, store_id,   -- in either order
      created_at)          -- last


This will avoid the sorting that is currently necessary.  (See EXPLAIN SELECT ...)

I can't remove the single-column index.

Do you mean that your fingers don't work?  Your boss will slap your hand if you try?  You don't have permissions?  It comes back when you do remove it?  The FOREIGN KEY gets in the way?  What?

Cardinality

Fake news.

Within a composite index, cardinality is irrelevant.

When comparing two indexes, cardinality is important, but there are usually better ways to optimize, such as using a composite index.  So, again, fake news.

Back to the question

Your experiments showed that either INDEX(store_id) or INDEX(store_id, deleted) would be used.  Given a choice between the two of them, the Optimizer will pick the smaller one (on the presumption that the amount of effort is slightly less).  Without a choice (ie, when you had deleted the smaller one), the Optimizer happily picked whichever one is left.

So, to avoid wasting disk space, DROP the shorter (single-column) INDEX.  Meanwhile this query will continue to work efficiently.

"Why isn't store_deleted_idx used in the first case?" -- Because of the OR.

More on indexing

http://mysql.rjweb.org/doc.php/index_cookbook_mysql discusses how getting all the way through the WHERE (after getting rid of OR) lets the index get to the ORDER BY, and if you get through the ORDER BY (by tacking on created_by), you can get to LIMIT.  Then it will read only 10 rows, not the whole table!