I have created a connected app (client id and client secret). When I login from developer edition, I can able to access rest API but when I try with Professional edition I am getting the error as described above. Somewhere I found we have to submit the case in partner community with consumer secret and consumer client detail. But still, we haven't received any response. Are you doing the wrong step?
The details of how to request access to the REST API in Professional Edition orgs is found here: Accessing the REST API in Group and Professional Editions If you have not heard back on your partner support case requesting access, add a comment to your case and request a status update.