Compare elements of each list of lists to corresponding ones in different list
Your algorithm uses the list.index function to get the indices of the sublists which is an \$O(n)\$ operation. You are also iterating through all the rows and columns of the data which is an \$O(k \times m)\$ operation where \$k\$ is the number of rows and \$m\$ is the number of columns. In the end it is an \$O(n \times k \times m)\$ algorithm.

In my algorithm getting the intersection of the keys is an \$O(\min(\text{len}(A), \text{len}(B)))\$ complexity then iterating the sublists is an \$O(m)\$ which results in an \$O(\min(\text{len}(A), \text{len}(B)) \times m)\$ complexity.

My alternate solution is based on the fact that the first element of each sublist is unique.
I would structure the data in a different way and use dictionaries instead of lists.
As each first element is unique this would be the key and the rest of the sublist would be the value in the dictionary.
After inserting all the data in the dicts, taking the intersection of the keys would result in a (hopefully) smaller set of data.
The output would be also a dictionary created while iterating through the resulting keys.

output = defaultdict(list) # from collections
keys = A.keys() &amp; B.keys() # intersect the keys
for key in keys:
    # create output based on sublists
    output[key] = ['ok^ok' if a==b else '{}^{}'.format(a,b) for a,b in zip(A[key],B[key])]


For execution time I generated random strings for keys and values. Each key and sublist element was a randomly generated unique string of length 10. Each key had 50% chance to be included in both A and B and each sublist element also had a 50% to be the same for the corresponding element in the other dictionary. I created 50k keys and 104 sublist element for each key.

Generating the data took me around 26 seconds and creating the output took less than 1 second. The results depend on the matching key ratio of the two datasets but it never took more than 2 seconds to finish.