In the spirit of Tim Toady I found another way to solve the problem:

# Load constants
my %CONSTANT = (
    %{ Win32::OLE::Const->Load( "Microsoft Excel 11.0 Object Library" 
+) },
    %{ Win32::OLE::Const->Load( "Microsoft Office 11.0 Object Library"
+ ) },
    %{ Win32::OLE::Const->Load( "Microsoft Word 11.0 Object Library" )
+ },
);


# Get the table selection
$table->{Range}->Select();
my $selection = $word->ActiveWindow->{Selection};

# Get the text from the previous paragraph
my $prev_text = $selection->Previous( $CONSTANT{wdParagraph} )->{Text}
+;
[download]

Personally I would (and do) put it in a loop, That tracks backwards looking for the title. Perhaps there is a few blank lines between the title and the associated table?

# Example title regex
my $title_regex = qr/ Table \s ( \d+ ) :  /xms;

# Check only the five previous matches ( Could also keep checking unti
+l you find a match with a while )
for ( 0 .. 5 ) {
       # Get previous paragraph
       # Get Text

       # Exit or do somthing else if the title is found.
       last if $text =~ $title_regex;
}
[download]

I'll let you fill in the blanks...
- John