How to create new page in Confluence using their REST API?

My suspicion is that you are not using a new-enough version of Confluence. The REST API for creating a new page was introduced in Confluence 5.5 (which came out 8 days ago). The API documentation is versioned, and you should always use the version corresponding to your Confluence release. The 5.5 API docs include the page creation API you need, but older versions do not. You can change the version in the above URL to get the API version matching your Confluence release.

Confluence 5.4 and prior also used a different root prefix for the REST API (/rest/prototype/1/content) which is one possible reason for getting a page not found error.

The example on the Atlassian site is also confusing because it includes an extra "/confluence" in the URL, which you would only need if Confluence were set up with a context path. This could also result in a page not found error if you were using Confluence 5.5+ (although your post suggests that you already corrected for this).

Additionally, you need to tell Confluence that you are using the basic authentication method by adding a special os_authType query parameter.

The following example works for me on Confluence 5.5 (don't forget to change the port and space key as appropriate).

For safety, I also added the appropriate content type to the Accept header, although this seems to be not needed in practice.

curl -v -u admin:admin -X POST -H 'Content-Type: application/json' -H 'Accept: application/json' -d'{"type":"page","title":"new page","space":{"key":"ATTACH"},"body":{"storage":{"value":"<p>This is a new page</p>","representation":"storage"}}}' "http://localhost:8090/rest/api/content/?os_authType=basic"

To answer your last question, the specific API that creates the page is determined by the URL itself and the request method. For example, performing a GET on "/rest/api/content" will fetch an existing page (given the appropriate query parameters), while performing a POST will create a new page.

EDITED TO ADD:

See also my comment below for how to create a page as a child of another existing page, as opposed to just at the top level of a space.

Not REST api, but a work around I put together. Try this:

To move a page as child page

curl -X GET \
'<your-confluence-URL>/pages/movepage.action?pageId=<page-to-be-moved-pageId>&spaceKey=<target-space-key>&targetTitle=<target-title-of-parent-page>&position=append' \
-H 'authorization: Basic <encoded-username-password>' \ 
-H 'x-atlassian-token: no-check'

To move a page as top level page in space

curl -X GET \
'<your-confluence-base-URL>/pages/movepage.action?pageId=<page-to-be-moved-pageId>&spaceKey=<target-space-key>&position=topLevel' \...