bash aliases do not expand even with shopt expand_aliases

It doesn't seem work if you set the alias on the same line as it's used. Probably something to do with how aliases are expanded really early in the command line processing, before the actual parsing stage. On an interactive shell:

$ alias foo
bash: alias: foo: not found
$ alias foo='echo foo'; foo         # 2 
bash: foo: command not found
$ alias foo='echo bar'; foo         # 3
foo
$ foo
bar

Note how the alias used is one line late: on the second command it doesn't find the alias just set, and on the third command it uses the one that was previously set.

So, it works if we put a newline within the -c string:

$ bash -c $'shopt -s expand_aliases; alias foo="echo foo";\n foo'
foo

(You could also use bash -O expand_aliases -c ... instead of using shopt within the script, not that it helps with the newline.)

Alternatively, you could use a shell function instead of an alias, they're much better in other ways, too:

$ bash -c 'foo() { echo foo; }; foo'
foo

Turning my comment into an answer, as suggested by ilkkachu.

The Bash manual (linked to in the question) does provide an explanation of how the aliases are handled when there is an alias definition and a command on the same line.

Quote (slightly formatted for clarity):

The rules concerning the definition and use of aliases are somewhat confusing. Bash always reads at least one complete line of input, and all lines that make up a compound command, before executing any of the commands on that line or the compound command.

Aliases are expanded when a command is read, not when it is executed. Therefore, an alias definition appearing on the same line as another command does not take effect until the next line of input is read. The commands following the alias definition on that line are not affected by the new alias.

This behavior is also an issue when functions are executed. Aliases are expanded when a function definition is read, not when the function is executed, because a function definition is itself a command. As a consequence, aliases defined in a function are not available until after that function is executed.

To be safe, always put alias definitions on a separate line, and do not use alias in compound commands.

ilkkachu's answer provides multiple possible solutions to this problem.