It was a little mind-numbing to check this code, but it looks correct.

Please fix two nits for better readability.   For review purposes, it was nice to have changes stand-out, but for the final code I would like to combine the two comments and the two new_allocated assignments into a single comment and single assignment:

      /* The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
         Note: new_allocated won't overflow because the largest possible value
               is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
      */
     new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

Secondly, please rename the "size" variable to something like "num_allocated_bytes".  It is confusing to have "newsize" mean the number of elements actually used while having "size" mean the number of bytes actually allocated (including the overallocation).