Simple question and the answer is layer 3 of course, but can we say that PAT is working on layer 4 also because it deals with port numbers which is a layer 4 function?
Or is it only a layer 3 protocol?
NAT works at layer 3 because it is modifying the IP header. If you use PAT you could argue that it is working at layer 4 as well because it MIGHT change the source port of the packet in case it is not unique.
Several internal addresses can be NATed to only one or a few external addresses by using a feature called Port Address Translation (PAT) which is also referred to as "overload", a subset of NAT functionality.
PAT uses unique source port numbers on the Inside Global IP address to distinguish between translations. Because the port number is encoded in 16 bits, the total number could theoretically be as high as 65,536 per IP address.
PAT will attempt to preserve the original source port, if this source port is already allocated PAT will attempt to find the first available port number starting from the beginning of the appropriate port group 0-5111, 512-1023 or 1024-65535.
If there is still no port available from the appropriate group and more than one IP address is configured, PAT will move to the next IP address and try to allocate the original source port again. This continues until it runs out of available ports and IP addresses.
So the port will only be modified in case it is not unique.
This link to Cisco is a pretty good overview of NAT.
Nat is a cross-layer process. It involves at least layers 3 (IP) and 4 (TCP, UDP, etc). In some cases it can also involve layer 7 (application).
A one to one NAT needs at minimum to modify the IP addresses (layer 3), IP checksums (layer 3) and TCP/UDP checksums (layer 4).
A one to many NAT needs at minum to modify the IP addresses (layer 3), IP checksums (layer 3), TCP/UDP ports (layer 4) and TCP/UDP checksums (layer 4).
Such a minimal NAT will break many things (for example active-mode ftp). Most NATs will therefore go beyond the basics and also perform translation and tracking of at least some IP addresses in application data (layer 7).
Think about how this has to be consistent across packets from the same device... at least within sessions. You could argue, therefore, that you should place this at level 5 or even higher. Just because it reaches down to modify IP headers shouldn't disqualify it from consideration from the higher layers. Lower layers might not know anything about higher layers, but higher layers can know and manipulate the lower. Indeed, Layer 6 seems appropriate. From wikipedia:
Application-layer entities may use different syntax and semantics if the presentation service provides a big mapping between them.
Mapping between addresses, even if the addresses are at level 3 instead of level 7, seems a very presentation-layer thing to do.