BQN, 14 bytes

⊣`⊸≡≠⥊¨·⊔˝·⊐˘⍉

BQN online REPL

Idea: Assuming the input has the form of the test cases, this is a BQN array where the columns contain elements of A and B respectively. Classify the A and B coordinates into integer IDs. Group the B-IDs according to their corresponding A-IDs. Cycle each resulting group vector to the length of the original input. Check if all these new, normalized vectors are identical.

Uiua, 19 bytes

=1⧻◴°⍉˙⊞÷⬚0⊕°⊚∩⊛≡°⊟

Try it!
Same alg as jan's uiua solution.

∩⊛≡°⊟ # unzip and map to 0-n
⬚0⊕°⊚ # group the seconds by the firsts and take the counts (filling with zeroes)
˙⊞÷    # divide each pair of groups
°⍉     # untranspose (bring the count-wise axis to the front)
=1⧻◴   # check if they all match

°⍉ untranspose is kind of weird to explain here, but here's a visualization of how the axes change over the program:

∩⊛≡°⊟ # 2xN -> N, N
⬚0⊕°⊚ # N, N -> PxQ (P and Q are the number of distinct values in A and B)
˙⊞÷    # PxQ -> PxPxQ
°⍉     # PxPxQ -> QxPxP
=1⧻◴   # QxPxP -> () (scalar)

Python, 76 bytes

Thanks @att for -1.

lambda L,S=sorted:S(K:=[a+b for a in L for b in L])==S((x*3)[::3]for x in K)

Attempt This Online!

Python, 77 bytes

Thanks @Jonathan Allan for -1.

lambda L:sorted(K:=[a+b for a in L for b in L])==sorted((x*3)[::3]for x in K)

Attempt This Online!

Original

Python, 84 bytes

lambda L:all((C:=L.count)(a)*C(b)==C((a+b)[::3])*C((b+a)[::3])for a in L for b in L)

Attempt This Online!

which implements the main idea more directly.

How?

Checks for every pair of pairs (a,b),(c,d) in the given list L whether the products of counts #(a,b) x #(c,d) and #(a,d) x #(c,b) are equal.

Clearly, this is necessary for L to be a cartesian product.

For sufficiency, observe #(a,b)/#(c,b) = #(a,d)/#(c,d) for any b,d so row a is a multiple of row c. Since this holds for any a,c the matrix of counts has rank <= 1 and can be written as an outer product.

Uiua, 45 characters

F←⍣(×/×♭⊞(⊞=.÷).:/×♭⊞=.⊕(∩⊏,⟜⍏⊕(⊃⊢⧻)⊛.)⊛°⊟⍉)0

Try it here!

Using the algorithm:

If, when the pairs are grouped according to first digit, the groups contain second digit multisets whose item counts are multiples of each other, the set is a cartesian product.

Which is apparently less golfy than some of the other algorithms that have been used.

Nekomata + -e, 9 bytes

ŤđᵃSᵒÐj↕=

Attempt This Online!

A port of @DLosc's Brachylog answer to Nekomata. Unfortunately, Nekomata doesn't have a built-in for Cartesian product.

ŤđᵃSᵒÐj↕=
Ť           Transpose
 đ          Unpair
  ᵃS        Take a subset of each of the two lists
    ᵒÐ      Generate a 2d array of all possible pairs
      j     Concatenate
       ↕    Permute
        =   Check if equal

Nekomata + -e, 10 bytes

↕JᵐŤŤđ≡¿ᵐ≡

Attempt This Online!

↕JᵐŤŤđ≡¿ᵐ≡  Take [[1,4],[1,6],[2,4],[7,4],[7,6],[2,6]] as an example
↕           Permute
                One possible output: [[1,4],[1,6],[2,4],[2,6],[7,4],[7,6]]
 J          Split into a list of sublists
                One possible output: [[[1,4],[1,6]],[[2,4],[2,6]],[[7,4],[7,6]]]
  ᵐŤŤ       Transpose twice; the original innermost level now becomes the outermost
                [[[1,1],[2,2],[7,7]],[[4,6],[4,6],[4,6]]]
     đ      Unpair
                [[1,1],[2,2],[7,7]], [[4,6],[4,6],[4,6]]
      ≡     Check that all elements in the second list are equal
                [[4,6],[4,6],[4,6]] passes the check
       ¿    And
        ᵐ≡  For each element in the first list, check that all elements are equal
                [[1,1],[2,2],[7,7]] passes the check

Vyxal 3, 11 bytes

Tᵛ⁺/Ẋᵛ/Ẋ$Ṗ⁾

Outputs empty list for falsey, nonempty list for truthy. Try it Online!

Explanation

Rough port of my Brachylog answer:

Tᵛ⁺/Ẋᵛ/Ẋ$Ṗ⁾
T            Transpose into two lists of elements
 ᵛ⁺          Powerset (all subsets) of each
   /Ẋ        Fold on Cartesian product (all possible pairs of subsets)
     ᵛ/Ẋ     Fold each on Cartesian product (Cart. prod. of each pair)
        $    Swap, pushing original input again
         Ṗ   List of all permutations
          ⁾  Set intersection

That is, some permutation of the input matches one of the Cartesian products.

Jelly, 9 bytes

ŒṬ€SẸƇÆrE

Try it online!

Builds a 2D matrix where each element represents how many times its coordinates appear in the original array, and then passes it to Dennis's rank-1 matrix test. In modern Jelly, Ðf has been superseded by Ƈ.

ŒṬ€SẸƇÆrE    Input: a list of pairs
ŒṬ€          For each pair [a,b], create a matrix with a rows and b cols
             filled with zeros, but with a 1 at the bottom right corner
   S         Sum; pad with zeros as necessary
    ẸƇÆrE    Dennis's rank-1 matrix test:
    ẸƇ       Remove all-zero rows
      Ær     Interpret each row as a polynomial and find its complex
             roots with multiplicity
        E    Test if they are all eqaual

Some rows may be shorter after S (e.g. for input [[1,2], [3,4]]), but it is not a problem because the rightmost element is treated as the highest power, so [0, 0, 0, 1] (x^3) and [0, 1] (x) have roots [0,0,0] and [0] respectively.

Jelly, 12 bytes

ZṬ€S:g/$Ɗƙ/E

Try it online!

I don't see this getting any shorter, but at least it ties Jonathan Allan's performant variant with a bit more performance.

Z       Ɗƙ/     Group the second column by the first column, and for each group:
    :           Divide
 Ṭ€S            the order-independent multiplicities of the elements
     g/$        by the multiplicities' GCD.
           E    Are the results of every group equal?

Brachylog, 6 bytes

\⊇ᵐẋp?

Try it online!

Explanation

\⊇ᵐẋp?
\       Transpose the list of pairs into a pair of lists, each containing the
        elements of one of the multisets (possibly more times than necessary)
 ⊇ᵐ     Take some subset of each list
   ẋ    Cartesian product of those subsets
    p   Take some permutation
     ?  Assert that the result equals the input

Charcoal, 27 bytes

⬤θ⬤θ⁼×№θι№θλΠＥ²№θＥ²§⎇⁼νπιλπ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a Cartesian product, nothing if not. Explanation: Port of @Albert.Lang's Python answer.

 θ                          Input list
⬤                           All values satisfy
   θ                        Input list
  ⬤                         All values satisfy
      №                     Count of
        ι                   Outer value
       θ                    In input list
     ×                      Multiplied by
         №                  Count of
           λ                Inner value
          θ                 In input list
    ⁼                       Equals
              ²             Literal integer `2`
             Ｅ              Map over implicit range
               №            Count of
                  ²         Literal integer `2`
                 Ｅ          Map over implicit range
                      ν     Inner index
                     ⁼      Equals
                       π    Innermost index
                    ⎇       If true then
                        ι   Outermost value
                         λ  Else outer value
                   §        Indexed by
                          π Innermost index
                θ           In input list
            Π               Take the product
                            Implicitly print

JavaScript (Node.js), 84 bytes

x=>!x.some(e=>(g=c=>x.map(t=>s+=t.every((u,i)=>i-c|u==e[i]),s=0)|s)``*g(1)-g()*g(2))

Try it online!

-6 from att
-1 from Arnauld

05AB1E, 14 (or 13) bytes

ø€æ`âε`â{I{Q}à

Try it online or verify all test cases.

Should have been 13 bytes (but a lot slower) if it weren't for a bug in the (flattened) maximum builtins à/Z/M for a list of lists containing empty lists, by changing {I{Q to œ€Q: (don't) try it online.

Explanation:

ø             # Zip/transpose; swapping rows/columns of the (implicit) input
 €            # Map over both inner lists:
  æ           #  Get its powerset
   `          # Pop and push both powersets separately to the stack
    â         # Take the cartesian product to create all pairs of lists
     ε        # Map over each pair of lists:
      `       #  Pop and push both lists separately to the stack
       â      #  Take the cartesian product to create all pairs of values
        {     #  Sort the list of pairs
         I    #  Push the input
          {   #  Sort its pairs as well
           Q  #  Check if both sorted lists of pairs are the same
     }à       # After the map: check if any is truthy by leaving its maximum
              # (after it is output implicitly as result)

        œ     #  Get all permutations of this list of pairs
         €    #  Inner map over each pair:
          Q   #   Check if this list of pairs is equal to the (implicit) input-list
     }à       # After the map: check if any inner value is truthy (flattened max)

Wolfram Language (Mathematica), 25 bytes

MatrixRank@BinCounts@#<2&

Try it online!

Form a matrix whose entries correspond to the number of times a pair is present in the input. This is a cartesian product of multisets iff all rows/columns of that matrix are linearly dependent, i.e. its rank is at most 1.

Since inputs are nonnegative integers, BinCounts conveniently returns a matrix where (0-indexed) \$i,j\$ is the number of times \$(i,j)\$ appears in the input.

Jelly, 11 bytes

FŒPpþ`ẎṢ€iṢ

A monadic Link that accepts a list of pairs and yields 0 (falsey) if not a possible Cartesian product or a positive integer (truthy) if it is.

Try it online! (too slow for any more than four pairs) Or see a reduced test-suite.

How?

FŒPpþ`ẎṢ€iṢ - Link: list of pairs, A
F           - flatten {A} -> all elements
 ŒP         - powerset -> all multisets of all elements
     `      - use as both arguments of:
    þ       -   table of:
   p        -     {muliset 1} Cartesian product {multiset 2}
      Ẏ     - tighten from a table to a list of the Cartiesian products
       Ṣ€   - sort each
          Ṣ - sort {A}
         i  - 1-indexed index of the first occurrence of {sorted A} in
              {sorted products}, or 0 if not found

A slightly faster 12 byte version

ZŒP€pþ/ẎṢ€iṢ

Same I/O as the 11 byter.

Try it online! Or see the test-suite.

How?

ZŒP€pþ/ẎṢ€iṢ - Link: list of pairs, A
Z            - transpose A -> [left elements, right elements]
 ŒP€         - powerset of each -> [potential left m-sets, potential right m-sets]
      /      - reduce by:
     þ       -   table of:
    p        -     {potential left m-set} Cartesian product {potential right m-set} 
       Ẏ     - tighten from a table to a list of the Cartiesian products
        Ṣ€   - sort each
           Ṣ - sort {A}
          i  - 1-indexed index of the first occurrence of {sorted A} in
               {sorted products}, or 0 if not found

Vyxal G, 82 bits^v2, 10.25 bytes

fṗƛṖƛøṖƛΠ?⁼}f

don't bother to Try it Online!

Bitstring:

0111011101101100110011101001011010010100001011000101000101000010100100111100011011

So this times out for anything where there's more than two pairs in the input. Basically, anything larger than a 2x2 matrix (iykyk). Possibly because it checks the cartesian product of all possible partitions of all permutations of the powerset of the flattened input. That's like at least \$O((2^n)!)\$ which is already pretty slow.

Most probably high very likely to be golfable somehow.

Explained

fṗƛṖƛøṖƛΠ?⁼}f­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁣⁢​‎‏​⁢⁠⁡‌­
fṗ             # ‎⁡Powerset of the flattened input. Already slow for large inputs. 
  ƛ            # ‎⁢To each set in the powerset:
   Ṗ           # ‎⁣ Get all permutations of that set. Very slow for large inputs with big subsets.
    ƛ          # ‎⁤ To each permutation:
     øṖ        # ‎⁢⁡  Get all the possible ways to split the list. Extremely slow for large inputs
       ƛ       # ‎⁢⁢  To each partition:
        Π      # ‎⁢⁣   Take the cartesian product. For large inputs this means it'll probably never terminate in the lifetime of the universe 
         ?⁼    # ‎⁢⁤   Is that cartesian product equal to the input? 
           }f  # ‎⁣⁡Close all the maps and flatten
# ‎⁣⁢If by some chance all of the above terminates, the G flag gets the maximum of that list. This is basically an any() check
💎

Created with the help of Luminespire.

Python 3, 174 bytes

def f(a):x,y=zip(*a);return any(sorted(a)==sorted([[k]+[l]for k in i for l in j])for i in g(*x)for j in g(*y))
g=lambda x=0,*a:x and[i+j for i in[[x],[]]for j in g(*a)]or[[]]

Try it online!

f is the main function and g returns all subsets for a given input.