Nope, that's not your sensor...the oddly shaped stars near the edges of the frame are an example of coma...here's a good explanation
of it from lensrentals.com. I'm guessing since that's an APS-C lens that just happens to cover a FF image circle at 16mm that they didn't make much of an attempt to correct for the coma.
That being said, if you stop down a couple of stops it should clean up fairly well...that obviously eliminates it's usefulness for astrophotography purposes, but as a daytime lens, it may still be useable.
I have a 10-20mm Sigma f/3.5 that I've tried on my 6D and I'm able to get an image down to about 14-15mm before I see any major vignetting...I haven't checked it for coma, but I suspect it suffers from the same issue your Tokina does. Here's another thread that talks about using a 1.4x teleconverted with the Sigma 10-20mm (not clear if it's the f/4-5.6 or the f/3.5 version) to use on a full frame camera.
I took my 6D and 10-20mm to the local Calumet a couple of years ago to try this out and I wasn't terribly impressed with the results wide open. It worked...but the corners weren't acceptable to me until I got to f/11 or so, so I ended up buying the Rokinon 14mm f/2.8 lens since I needed something wide for astrophotography. I can't recommend that 14mm lens enough, especially for the price.