Sending lightning payment between TOR lighning nodes, any specific setup required?
Is it possible the problem for that to be related to TOR, considering that I can connect to and open channels with public nodes just fine?

No, that's very unlikely. (and contradictory)
Are the channels you created announced ?
Are your two nodes connected to the network ? For a node to find a route it needs to be connected to the peer-to-peer network to trade gossip and build its view of the current state of the network (opened channels and whether they are active).
Without this information there is nothing for it to search routes in.
You can verify that your channels are announced with listpeers (the channels array), or by running listchannels &lt;scid&gt; on your first node (with scid the short channel id of a channel of your second node).
If listchannels returns an empty array you need to connect to some public nodes and wait for your node to sync gossip with the rest of the network.
Finally, as it'll surely be your next concern: be sure to have incoming capacity in at least one of your second node's channel :-).