###Code duplication

To be honest - yes, this code is rather messy, mostly due to the code duplication. at least you could've shortened it by using existing SQL, like

$sql = "SELECT company.id, company.name, inn, ceo, city, phone
      FROM company
      LEFT JOIN address ON company.id = address.company_id
      LEFT JOIN contact ON company.id = contact.company_id
      WHERE
        MATCH (company.name, inn, ceo) AGAINST (:searchTerm)
        OR MATCH (city, street) AGAINST (:searchTerm)
        OR MATCH(contact.name, phone, email) AGAINST (:searchTerm)";
$stmt = $pdo->prepare($sql);
// ...
$sql .= " ORDER BY id DESC LIMIT $starting_limit, $limit";
$stmt = $pdo->prepare($sql);

###Performance problems

But the biggest problem with this code is not its structure but its ability to kill your server. Getting the number of rows returned by SELECT query is the most misused functinality in PHP.. Aside of the fact it is most of time just pointless, in a case like yours it could be dangerously harmful. Let's take your code, that looks quite simple and innocent:

$sql = "SELECT * FROM company";
$stmt = $pdo->prepare($sql);
$stmt->execute();
$total_results = $stmt->rowCount();

What does this code do? It is merely selecting all rows from the table and sending them to PHP, so it will be able to count them. Imagine there will be 100000 rows, with 1k data in each. It will result in sending 1G of data from database server to PHP. Not only it will consume a lot of resources in the process but most likely it will overflow the memory limit in PHP and make it die with the fatal error.

So you should never ever use rowCount() for pagination. Instead, you must ask a database to get you the number of rows.

###Query builder

In order to make this code more maintainable (so every query part would be written only once), we must split the SQL into distinct parts and then use them to construct the particular query:

$select_count = "SELECT count(*) FROM company";
$select_data = "SELECT company.id, company.name, inn, ceo, city, phone
          FROM company
          LEFT JOIN address ON company.id = address.company_id
          LEFT JOIN contact ON company.id = contact.company_id";
$where = "WHERE MATCH (company.name, inn, ceo) AGAINST (:searchTerm)
            OR MATCH (city, street) AGAINST (:searchTerm)
            OR MATCH(contact.name, phone, email) AGAINST (:searchTerm)";
$order_limit = "ORDER BY id DESC LIMIT $starting_limit, $limit";

if (isset($_GET['search'])) {

    $parameters = [':searchTerm' => $_GET['search']];
    $sql_count = "$select_count $where";
    $sql_data = "$select_data $where $order_limit";

} else {

    $parameters = [];
    $sql_count = "$select_count";
    $sql_data = "$select_data $order_limit";
}

$stmt = $pdo->prepare($sql_count);
$stmt->execute($parameters);
$num_results = $stmt->fetchColumn();
$total_pages = ceil($num_results/$limit);

$stmt = $pdo->prepare($sql_data);
$stmt->execute($parameters);
$results = $stmt->fetchAll();

###Better separation between HTML and database stuff

The rest is your code is Okay, I would only remove any mention of a database stuff from HTML. So I would rather get all the rows into array first and than just iterate over it in HTML.

        <tbody>
        <?php foreach ($results as $row): ?>
            <tr>
                <td scope='row'><?=$row['inn']?></td>
                <td><a href="company.php?id=<?=$row["id"]?>"><?=$row['name']?></a></td>
                <td><?=$row['ceo']?></td>
                <td><?=$row['city']?></td>
                <td><?=$row['phone']?></td>
            </tr>
        <?php endforeach ?>
        </tbody>