How to find how many times an object's path crosses another?
This can be done by what I'd call "accelerated replay" (I'm making up this term).

Let's suppose the movement of each object is piecewise linear: each object moves in a straight line at a constant speed for a while, then changes direction and moves in a different direction at a different speed, etc.  So, object $i$'s path can be specified a sequence of times $t_{i,0},t_{i,1},\dots,t_{i,n}$ at which the object changes direction; between times $t_{i,j}$ to $t_{i,j+1}$, the object is moving in a straight line (with known endpoints) at a constant speed.  The algorithm can be generalized to allow each individual piece of the path to be curved or other shapes as well, but it's easiest to describe in this setting.

So, let's take the union of all of the times $t_{i,j}$ and sort them.  In this way, we get a set of "events", where each "event" corresponds to an object changing direction/speed.  Now, we're going to replay all of the object movements.  However, we're going to "fast forward" through all of the times that fall between two adjacent events.  In other words, we're going to iterate through the events in time order.

At a single step of the algorithm, we're going to be processing a particular event, say the event at time $t_{i,j}$ where object $i$ changes direction.  We know the line segment that each of the other objects are currently on; and we know the line segment that object $i$ will travel on after time $t_{i,j}$.  So, for each other object $i'$, compute the location where the lines for objects $i$ and $i'$ intersect, check the time when that will happen, and check whether that time is before the end time for both line segments; if so, you've found a cross-over.  Notice that finding the intersection point of two line segments can be done in constant time ($O(1)$ time).  Once you've done that, you've taken into account all cross-overs that can occur until the next event.  So, no need to continue simulating what happens in any future time, until the next event.  So, fast-forward to the next event, and then do the same thing for the next event.

The total running time will be $O(nm)$, where $n$ is the number of objects and $m$ is the total number of events.  Or, if you expect $q$ events per object (i.e., $q$ changes of direction), then the total running time will be $O(n^2q)$.  Since you have only a few hundred objects, that should be quite reasonable.

It's plausible to me that it might be possible to reduce this to something more like $O(nq \log n)$, using techniques from computational geometry (e.g., Shamos-Hoey etc.), if that were really necessary -- but I haven't tried to think about whether that's possible, as given the numbers you listed in your question, the algorithm above should be fine.

If you want to find "points of closest approach" instead of "crossovers", it's easy to adjust the above algorithm to do that.  Given two line segments, it is easy to find their point of closest approach in $O(1)$ time, so then you just apply the same ideas as before.  If you want to deal with curved trajectories, that is also possible; if you have two curved lines that are parts of a circle, it is also possible to find whether they intersect in $O(1)$ time using some trigonometry, so again you can generalize the above algorithm to handle that as well.

There are probably many pragmatic ways one could speed this up, e.g., by using quadtrees to separate the plane into multiple regions and map each part of the path to the region(s) it visits, and then only look for crossovers within each region.