Credit to sjcTheos for his research (code finding, spreadsheet work, image to game index matching) and for discovering this trick. Here are the 5 sets of spawns that can appear. Note that these sets only apply to maps with 4 potential spawn points, not to all maps!
As a general rule, to completely identify which spawn set you have, you will need to visit one even and one odd numbered map (Star worlds are numbered 8).

	0	1	2	3	4
A5
A6
A7
B4
B5
B6
B7
B Star
C1
C2
C3
C4
C5
C6
C7
C Star

Let's get technical

The reason this works is because of how Paint RNG is seeded in Talos. Here's the Lua code that determines paint spawns:

    -- nothing to do if messages are not available for current world
    if not talPlayerMessagesAvailableForCurrentWorld(worldGlobals.worldInfo) then
      return
    end

Exit program if player is done with the current world.

    local function RandomFomStringChars(str, multiplier)
      local len = #str
      local sum = 0
      local offset = 32
      for i = 1, len do
        sum = (string.byte(str, i) - offset)*multiplier
      end
      return sum
    end

This function creates an add-in seed which is supposed to be based on the world name. However, this calls sum = not sum = sum +, and so it in fact only uses the last character in the world name, in this case the world number.

    local function ShowPaintBucketIfNecessary()

      -- paint buckets can onlys be unlocked if enough messages are unlocked
      if talGetUnlockedPlayerMessagesCount(worldGlobals.worldInfo) < 5 then
        -- paint item was not shown
        return false
      end

Exit function if player doesn't have paint unlocked.

      -- talosProgress : CTalosProgress
      local talosProgress = nexGetTalosProgress(worldGlobals.worldInfo)
      local randomSeed = talosProgress:GetCodeValue("PaintItemSeed")
      if randomSeed == -1 then
        randomSeed = mthRoundF(mthRndF()*8909478)
        talosProgress:SetCode("PaintItemSeed", randomSeed)
      end
      local worldName = string.match(worldGlobals.worldInfo:GetWorldFileName(), "([^/]+)%.wld$")
      if randomSeed < 0 then
        randomSeed = -randomSeed
      end
      local multiplier = randomSeed % 8
      if multiplier == 0 then
        multiplier = 1
      end

This generates a random integer from 0 to 8909478, then from it creates a multiplier from 1-7. Note that a multiplier of 1 will occur with probability 1/4.

      local randomIndex = randomSeed + RandomFomStringChars(worldName, multiplier)
      if randomIndex < 0 then
        randomIndex = -randomIndex
      end

Now, the random integer from 0 to 8909478 is increased by the world name string times the multiplier. This means that the spawn set on A6 differs from A7, but not from B6.

      local randomPaintItemIndex = 1 + randomIndex % #worldGlobals.paintItems
      worldGlobals.paintItems[randomPaintItemIndex]:Show()
      -- paint item was shown
      return true
    end

Then, we convert the random number to a paint spawn. However, if there are 4 paint spawns (#worldGlobals.paintItems), then problems will arise because 4 and 8 are not coprime. For example, if we're on A3, then we calculate n + (n%8)*3, which will be 0 or 4 mod 8. The exception is if 8 | n and the multiplier is set to 1, in which case it will be 7 mod 8. Regardless, this is not an even distribution of values 0-7, and it is this behavior that causes uneven spawns.

    RunAsync(function()
      -- wait for all other scripts/items to boot
      Wait(Delay(0.00001))
      -- nothing to do if there are no paint items in the world
      if worldGlobals.paintItems == nil then
        return
      end
      -- show paint bucket if necessary at start
      if ShowPaintBucketIfNecessary() then
        -- since paint item was shown, there is no need to handle message unlocking
        -- events and check if paint item should be shown again
        return
      end
      -- wait for message unlocking event until paint bucket is shown
      while true do
        Wait(CustomEvent("PlayerMessageUnlocked"))
        if ShowPaintBucketIfNecessary() then
          break
        end
      end
    end)

This code just checks a couple of edge cases and only displays paint if needed.

So let's take a look at the arithmetic:

RNG % 8 Multiplier World Number:
Paint index = RNG +
Multiplier * World Number Paint spawn =
Paint index % 4

The modulo 8 creates 8 total spawn sets, and the modulo 4 means that sets 0/4, 1/5, 2/6, 3/7 are the same.
However, when the multiplier is 0 mod 8, it is set to 1, which differentiates sets 0 and 4 and gives us our 5 sets.

RNG % 8	Multiplier	World Number:	Paint index = RNG + Multiplier * World Number	Paint spawn = Paint index % 4