Why two objects behave like one? After a boolean operation, I had a quite "broken" object, reverse sides which weren't fixed by "fix normals" etc. I decided to create a fresh object, in a hope that it will turn out better this time (the cube to the left). But these two objects are somewhat linked.

For example, why selecting one of these objects selects also the other one? Why there is only one "Cube" in the menu?
You added the new cube while still in Edit Mode.
So both meshes are now part of one object - as shown in the Outliner.

You can easily split them into separate objects through
Mesh > Separate > By Loose Parts