I need to use VirtualProtect, and my question is about the address of the region passed to the function. It says (on MSDN) "an address that describes the starting page", does it have to be the address of the beginning of the page or could it be any address in that page? In other words, should I first use VirtualQuery to determine the starting address of the page?
You don't need to pass in the base address of the page. VirtualProtect will accept any address within the page. The description of the dwSize parameter makes that clear:
The region of affected pages includes all pages containing one or more bytes in the range from the lpAddress parameter to (lpAddress+dwSize). This means that a 2-byte range straddling a page boundary causes the protection attributes of both pages to be changed.
If you're able to have a two-byte range that straddles a page boundary, then it must be possible for lpAddress to be just one byte before the end of a page. Pages can't be just one byte long, so it's not at the start of a page.