How to fix: “Partition does not start on physical sector boundary”

Sectors are the minimum unit of data that the disk hardware can read (what is actually on the disk platters or the SSD memory cells is a different question, but is not relevant at this point). When space is allocated on disk for a file, it is allocated in sectors; if your file is smaller than an (integral) multiple of the sector size, the last remaining bytes of a sector are wasted. In the old days when disks were a lot smaller, a 512-byte sector was a good compromise between the average file size and the acceptable waste (do not confuse the physical sector size with the filesystem block size). With increased density, 512-byte physical sectors have not made sense in the last 10-20 years; spinning drives have had 4KB (8 * 512 byte) sectors for a long time now. Even though you can access stuff on disk at pretty much arbitrary offsets, operations are slightly faster if you access them at sector boundaries.

You can change the partition start and end offsets to be a multiple of 8 sectors (or 4096 bytes, whichever unit gpart uses; I use parted) and remake the partitions, and everything will be happy!

You did not get your partitions back using TestDisk: they're a total jumble. You're better off using PhotoRec to restore individual files.

Good luck! (You'll need it, unfortunately...)