Concept that requires both a const and non-const overload to be present

The problem is that a const member function is always callable on a non-const object, so a requires expression using nonconstval.foo() can't distinguish "has a non-const overload" from "has only a const overload."

Instead of testing callability, test for the existence of a member function pointer with the exact signature you want using staticcast:

template 
concept HasNonConstFoo = requires {
    staticcast(&T::foo);
};
template 
concept HasConstFoo = requires {
    staticcast(&T::foo);
};
template 
concept Both = HasNonConstFoo && HasConstFoo;

This works because staticcast(&T::foo) selects specifically the non-const overload from the overload set. If only a const overload exists, the cast fails — a void (T::)() const is not convertible to void (T::)() (they are distinct types). And vice versa.

Godbolt demo (replace the concepts with the above)

With your test cases:

callfoo(mc);  // ✓ MyClass has both overloads
callfoo(nco); // ✗ NonConstOnly — missing const overload
callfoo(co);  // ✗ ConstOnly — missing non-const overload

Caveat: this approach requires taking the address of the member function, so it won't work if foo is a template, an overload set with different arities, or otherwise can't have its address taken unambiguously (though the staticcast itself is what resolves overload sets differing only in const-qualification, which is exactly this case).

Icharchurski answer can be generalized to template function through allowing to test for given instances:

template 
concept HasNonConstFoo =
    requires { staticcast(&T::foo); };
template 
concept HasConstFoo =
    requires { staticcast(&T::foo); };
template 
concept Both = HasNonConstFoo && HasConstFoo;

LIVE with template member functions
LIVE without

Note: It also allows to select the expected return type and arguments types.