I think first at all PyEval_Call* functions should be documented (issue11165). The documentation should recommend to use corresponding PyObject_Call* functions and explicitly describe the difference between PyEval_Call* and PyObject_Call* APIs.

Few releases after deprecating PyEval_Call APIs in documentation we can add the Py_DEPRECATED attribute for emitting compiler warnings. Few releases after deprecating in code we can remove PyEval_Call* declarations from headers, but keep exporting them in binary library. In Python 4 (or other major release that will break binary compatibility) they can be removed at all.