I am lacking a background in theoretical computer science but I would have liked to understand to what kind of theoretical objects C++ concepts corresponds to. Basically, C++ concepts allow to define a set of types that satisfy a list of constraints. So, from a theoretical standpoint, what C++ concepts correspond, or roughly correspond (and in that case what are the differences), to?
From a programming language theory perspective, as opposed to the computability perspective other answers and comments have offered, C++ templates combined with concepts correspond to bounded polymorphism or constrained genericity. Concepts themselves correspond to the constraints or bounds placed on a type.
A template is type-level function, parameterised by type that are constrained by a concept to implement a particular interface. When the template is applied to a type satisfying that concept, a new type results.
Templates+concepts are analogous to generics in Java, Scala or Eiffel. They differ from templates in earlier C++ because they allow constraints on the type parameters to be specified and checked, whereas C++ templates did not allow that. The benefit is better static checking that the program after applying the template will be well typed.
A good reference is Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press, Chapter 26: Bounded quantification.
C++ concepts map to recursively enumerable languages. Since the C++ type system is Turing complete, any property of types that can be interrogated during template instantition (size, parameters, etc.) can be run through an arbitrary program simulated in the type system.