So basically, you want to build a tuple, not parse one.
This is just a straightforward example of how you could convert your arr to a tuple of tuples. Here you should add some error checking at some point in time as well.
Py_ssize_t len = arr.size();
PyObject *result = PyTuple_New(len);
for (Py_ssize_t i = 0; i < len; i++) {
Py_ssize_t len = arr[i].size();
PyObject *item = PyTuple_New(len);
for (Py_ssize_t j = 0; j < len; j++)
PyTuple_SET_ITEM(item, j, PyInt_FromLong(arr[i][j]));
PyTuple_SET_ITEM(result, i, item);
}
(For Python 3 C API, replace PyInt_FromLong(arr[i][j]) with PyLong_FromLong(arr[i][j]))
Then you can build your args, like you did with the string. Instead of s for string, you would use O for PyObject * (or N if you don't want to increment the reference count):
pParam = Py_BuildValue("(O)", result);
Maybe boost::python could provide a simpler method, but I don't realy know the library myself.
returna list or to alter a list argument? If you don't know then returning is easier.