The relay
The datasheet clearly says, in the "Contacts" chapter:
Rated load: 16 A at 250 VAC
Rated carry current: 16 A
Max. switching current: 16 A
And there is no mention of a max switching power limit in the table. This is also confirmed by the graph "Maximum Switching Power" which shows a flat line at 16A, up to 250VAC and then it drops straight to 0.
So, yes, really, there is no possible doubt: This relay can switch 16A continuous. Note that, for relays of that size, 16A is not that huge.
Regarding thermal properties: they are often not clearly stated in the datasheets for those kind of relays. You just have to trust the manufacturer. It will certainly get hotter, but if that was 100° hotter, they would clearly mention it. Again, take it for granted it is rated up to 85°C operation, at full load. In the "Correct Use" chapter, they mention risk of temperature rise, but when the coil is activated for too long. They don't say anything about the contact, so it is fine.
Just for the fun, we could calculate the maximum dissipated power based on the given max contact resistance (100mΩ): that would be RI²: 0.1*16² = 25W. Of course, this seems impossible for a relay of that size. This is because the given max resistance is very conservative and measured with 1 A applied at 5 VDC (see note 1 on page 3 in datasheet). So the power will certainly be much less than that in your case, and you can safely assume that it will be fine.
The fuse
The fuse you selected seems fine. If you don't like the fact it is SMT, there are resettable fuses available in through-hole, but, often, they have hold current specified at 15A, not 16A.
The PCB traces
You are estimating the trace width correctly. But 10°C is very conservative for such a high-current application. You can certainly allow for more temperature rise on the trace, especially if the trace is short. Now, I wouldn't rely on using both top and bottom layers to reduce trace width, because the copper layer properties may be different on top and bottom (especially if the route is not exactly the same), and the current may not be equally shared. I could use two trace to lower the temperature rise, but I would still ensure that, if all current goes through only one trace, all requirements are still met.
Another solution (if it is a one-off) is thickening the trace with added solder all along it. This requires, of course, to design the trace without solder mask on the top of it, so this eventually means having more clearance between the two AC lines to eliminate creepage risk.
Inrush current
@Uwe raised a very good point regarding inrush current. Depending on your load, a much higher current than nominal may be required for a short time, when the load gets powered. This is the case for a lot of loads (SMPS supplies / big mains transformers / most lightnings / ...).
For the PCB trace, it isn't much of a problem, since it is for a short time only. For the fuse, this must be taken into account, but if you know your load, the fuse time/current curves on the datasheet will tell you if it works. For the relay, however, this may be a bigger problem. The datasheet of the relay you chose didn't mention anything about inrush, so you can't expect it to work reliably if your load creates singificant inrush. Here is an example of another, similarily speced latching relay, that clearly specifies inrush current: Panasonic ADW1.
Here is also a TE app note about relay contact life, that has interesting information regarding inrush.
Best Answer
That wide range between min and max current is a problem for most relays.
You have a couple of options.
Use a solid state device. MOSFETs are good at low potential and high currents.
Use two different relays: one for the pull-in, the other for holding.
You will have to control both relays individually - the smaller holding relay will pin much faster than the large relay.