<PAGE>   1
                                                                   EXHIBIT 10.19


                              PAGING NETWORK, INC.
                  AMENDED AND RESTATED 1991 STOCK OPTION PLAN

         1.      PURPOSE. The purpose of this Amended and Restated 1991 Stock
Option Plan (the "Plan") is to advance the interests of PAGING NETWORK, INC.
("PageNet") and its shareowners by providing an opportunity to all employees of
PageNet and its present and future domestic and foreign subsidiaries
(collectively, the "Company") to purchase the common stock of PageNet through
the exercise of options granted under this Plan and thereby have an incentive
to participate in and contribute significantly to the growth and financial
success of the Company. By encouraging such stock ownership, the Company seeks
to attract, retain and motivate employees with experience, ability and
leadership to share in the strategic and long-term performance objectives of
the Company and to more closely align the interests of the employees with those
of the shareowners.

         2.      EFFECTIVE DATE. The 1991 Stock Option Plan became effective on
August 23, 1991, the date it was adopted by the Board of Directors of PageNet.
The Plan was approved by the shareowners of PageNet on August 23, 1991. The
Plan was amended by the Board of Directors on January 26, 1993, subject to
shareowner approval, which was given on May 20, 1993. The Plan was further
amended by the Board of Directors on September 11, 1996 and on January 9, 1997,
subject to shareowner approval, which was given on May 22, 1997. This amendment
and restatement of the Plan will become effective on April 22, 1998, the date
it was adopted by the Board of Directors of PageNet, subject to the receipt of
approval by the shareowners of PageNet at the 1998 Annual Meeting of
Shareowners.

         3.      STOCK SUBJECT TO THE PLAN; TYPES OF OPTIONS. The shares that
may be granted under this Plan will not exceed in the aggregate 13,950,000
shares of the $.01 par value common stock of PageNet ("Common Stock"). Any
shares subject to an option which for any reason expires, is cancelled or is
terminated unexercised as to such shares may again be the subject of an option
under the Plan. The shares delivered upon exercise of options under this Plan
may, in whole or in part, be either authorized but unissued shares or issued
shares re-acquired by PageNet. In addition to the foregoing aggregate
limitation, no more than 500,000 shares may be granted under this Plan in any
one calendar year to any one eligible individual. The Plan allows for the
granting of nonqualified stock options ("nonqualified options"), the federal
income tax treatment of which is determined under Section 83 of the Internal
Revenue Code of 1986, as amended from time to time, and regulations thereunder
(the "Code"), and incentive stock options intended to qualify under Section 422
of the Code.
<PAGE>   2
         4.      ADMINISTRATION OF STOCK OPTIONS. The Plan will be administered
by the Stock Option/Compensation Committee of the Board of Directors of PageNet
(the "Board"), provided, however, that any authority or responsibility reserved
to the Committee under the Plan may be exercised in its discretion by the
Board, including but not limited to granting options under the Plan. The term
"Committee" means the entity administering the Plan pursuant to this paragraph,
whether the administrator is the Board or the Stock Option/Compensation
Committee.

         Subject to the provisions of the Plan, the Committee will have full
power to construe and interpret the Plan and to establish, amend and rescind
rules and regulations for its administration. Any decisions made with respect
thereto will be final and binding on the Company, the employee to whom the
option is granted (the "optionee") and all other persons. No employee will have
a right to be granted an option or, having received an option, a right to again
be granted an option under the Plan. Determinations made by the Committee under
the Plan need not be uniform and may be made selectively among eligible
employees under the Plan, whether or not such eligible employees are similarly
situated.

         5.      ELIGIBLE EMPLOYEES. Incentive options or nonqualified options,
or both, may be granted to all employees of PageNet and any present and future
domestic and foreign subsidiary of the Company. The Committee will have the
exclusive power to select the employees who may receive options under the Plan,
and may select the eligible employees individually or by groups or categories,
as determined by the Committee in its sole discretion.

         6.      DURATION OF THE PLAN. This Plan will terminate on the tenth
anniversary of shareowner approval of the amendment and restatement at the 1998
Annual Meeting of Shareowners, unless terminated earlier pursuant to Paragraph
11, and no options may be granted thereafter.

         7.      RESTRICTIONS ON INCENTIVE OPTIONS. With respect to incentive
options (but not nonqualified options) granted under this Plan, the aggregate
fair market value, determined as of the date each such option is granted, of
the shares with respect to which options are exercisable for the first time by
an employee during any calendar year will not exceed $100,000. If an incentive
option is granted with respect to shares exceeding the aforementioned $100,000
limitation, the portion of such option which is in excess of the $100,000
limitation will be treated as a nonqualified option. In the event that an
individual is eligible to participate in any other stock option plan of the
Company which is also intended to comply with the provisions of Section 422 of
the Code, the $100,000 limitation will apply to the aggregate number of shares
for which incentive stock options are granted under all such plans.

         8.      TERMS AND CONDITIONS OF STOCK OPTIONS. Options granted under
this Plan will be evidenced by instruments in such form and containing such
terms and conditions as the Committee will determine; provided, however, that
such instruments will evidence among their terms and conditions the following:



                                      2
<PAGE>   3
                 (a) PRICE. The purchase price per share of Common Stock
payable upon the exercise of each option granted hereunder will be as
determined by the Committee in its discretion, and will be not less than 100%
of the fair market value of the stock on the day the option is granted. Such
fair market value will be determined in accordance with procedures to be
established in good faith by the Committee in conformity with regulations
issued by the Internal Revenue Service with regard to incentive and
nonqualified options.

                 (b) NUMBER OF SHARES. Each option grant will specify the
number of shares to which it pertains.

                 (c) EXERCISE OF OPTIONS. Each option grant will be exercisable
for the full amount or for any part thereof and at such intervals or in such
installments as the Committee may determine; provided, however, that no option
will be exercisable with respect to any shares later than ten (10) years after
the date of the grant of such option. In case of an option not otherwise
immediately exercisable in full, the Committee may accelerate the
exercisability of such option in whole or in part at any time.

                 (d) NOTICE OF EXERCISE AND PAYMENT. An option will be
exercisable only by delivery of a written notice to the Company's Treasurer, or
any other officer of the Company designated by the Committee to accept such
notices on its behalf, specifying the number of shares for which it is
exercised. If said shares are not at that time effectively registered under the
Securities Act of 1933, as amended, the optionee will include with such notice
a letter, in form and substance satisfactory to the Company, confirming that
the shares are being purchased for the optionee's own account for investment
and not with a view to distribution. Payment will be made in full at the time
the option is exercised.  Payment will be made either by (i) cashier's or
certified check, wire transfer or other form of good and immediately available
funds, (ii) if permitted by the Committee and stated in the instrument, by
delivery and assignment to the Company of shares of Common Stock having a value
equal to the option price, (iii) if permitted by the Committee, by delivery of
a written notice stating that a market sell order has been placed with a broker
with respect to shares of Common Stock issuable upon exercise of the option and
that the broker has been directed to pay a sufficient portion of the net
proceeds of the sale to the Company in satisfaction of the aggregate exercise
price of the option or the portion thereof so exercised, or (iv) by a
combination of (i) and (ii) above. The value of the Common Stock for such
purpose will be its fair market value as of the date the option is exercised,
as determined in accordance with procedures to be established by the Committee.

                 (e) WITHHOLDING TAXES; DELIVERY OF SHARES. The Company's
obligation to deliver shares of Common Stock upon exercise of an option, in
whole or in part, will be subject to the optionee's satisfaction of all
applicable federal, state and local tax withholding obligations.

                 (f) NON-TRANSFERABILITY. Except as otherwise provided by the
Committee, no option will be transferable by the optionee otherwise than by
will or the laws of descent and distribution, and each option will be
exercisable during the optionee's lifetime only by the optionee (or the
optionee's guardian or legal representative).



                                      3
<PAGE>   4
                 (g) TERMINATION OF OPTIONS. Each instrument will contain
provisions for the termination of the options granted thereunder if the
optionee ceases for any reason to be an employee of or perform services for the
Company, no more favorable to the optionee than the following:

                          (i) if the optionee ceases to be employed by or
perform services for the Company for any reason other than for cause,
disability or death, the option will terminate on the earlier to occur of the
ninetieth day after the effective date of such resignation or termination and
the date of termination of the option pursuant to this Plan, and the option
may not be exercised thereafter;

                          (ii) if the optionee ceases to be employed by or
perform services to the Company for cause, which will mean willful misconduct,
dishonesty, insubordination, conviction of a felony, gross negligence in the
performance of duties as an employee, the material or repeated violation of
policies and practices of the Company, including its Code of Ethics, or the use
of illegal drugs or the illegal use of controlled substances, the option will
terminate on the day of such termination for cause;

                          (iii) if the optionee ceases to be employed by or
perform services for the Company because of any physical or mental disability
which would have entitled such employee to payment of disability benefits under
the Company's long-term disability plan or any similar plan of the Company
(regardless of whether such employee was then a participant in such plan), he
may at any time within a period of one year after such termination of
employment, or prior to the termination of the option pursuant to this Plan,
whichever is earlier, exercise his option to the extent that the option was
exercisable by him on the date he ceased to be employed by or perform services
for the Company; and

                          (iv) if the optionee dies at a time when the option
was already vested and exercisable, then his estate, personal representative
or beneficiary to whom it has been transferred pursuant to Paragraph 8(f) may,
at any time within a period of one year after the optionee's death, or prior to
the termination of the option pursuant to this Plan, whichever is earlier,
exercise it to the extent the optionee might have exercised it at the time of
his death;

provided, however, that notwithstanding anything to the contrary contained in
clauses (i), (ii), (iii) and (iv) above, the Committee may provide specifically
in an instrument governing an option grant for such other period of time during
which an optionee may exercise an option after termination of services as the
Committee may approve, subject to the overriding limitation that no option may
be exercised to any extent by anyone after the date of expiration of the
option.

                 (h) RIGHTS AS SHAREOWNER. An optionee will have no rights as a
shareowner with respect to any shares covered by his option until the date the
option has been exercised and the full purchase price for such shares has been
received by the Company.



                                      4
<PAGE>   5
         9.      STOCK DIVIDENDS; STOCK SPLITS; STOCK COMBINATIONS;
RECAPITALIZATIONS. Appropriate adjustment will be made in the maximum number of
shares of Common Stock subject to the Plan and in the number, kind, and option
price of shares covered by outstanding options granted hereunder to give effect
to any stock dividends, stock splits, stock combinations, recapitalizations and
other similar changes in the capital structure of PageNet after the effective
date of the Plan.

         10.     MERGER; SALE OF ASSETS; DISSOLUTION. Notwithstanding anything
to the contrary contained in this Plan, in the event of a "Change of Control,"
as defined herein, every option outstanding hereunder will become immediately
exercisable in full. In the event of a change in the Common Stock resulting
from a merger or similar reorganization, the number and kind of shares which
thereafter may be optioned and sold under the Plan and the number and kind of
shares then subject to options granted hereunder and the price per share
thereof will be appropriately adjusted, in such manner as the Committee may
deem equitable, to prevent substantial dilution or enlargement of the rights
available or granted hereunder.

         A "Change of Control" shall be deemed to have occurred if the event
set forth in any one of the following paragraphs shall have occurred:

                 (a) any Person is or becomes the Beneficial Owner, directly or
indirectly, of securities of PageNet representing 35% or more of the combined
voting power of PageNet's then outstanding securities (not including in such
securities beneficially owned by such Person any securities acquired directly
from PageNet), other than any Person who becomes such a Beneficial Owner in
connection with a transaction described in clause (i) of paragraph (c) below;
or

                 (b) the following individuals cease for any reason to
constitute a majority of the number of directors then serving: individuals who
on the date hereof constitute the Board, and any new director whose appointment
or election by the Board or nomination for election by PageNet's shareowners
was approved or recommended by at least two-thirds (2/3) of the directors then
still in office who either were directors on the date hereof or whose
appointment, election or nomination for election was previously so approved or
recommended (other than a new director whose initial assumption of office is in
connection with an actual or threatened election contest, including but not
limited to a consent solicitation, relating to the election of directors of
PageNet); or

                 (c) there is consummated a merger or consolidation of PageNet
or any direct or indirect subsidiary of PageNet with any other corporation,
other than (i) a merger or consolidation which would result in the voting
securities of PageNet outstanding immediately prior to such merger or
consolidation continuing to represent, in combination with the ownership of any
trustee or other fiduciary holding securities under an employee benefit plan of
PageNet, at least 65% of the combined voting power of the securities of PageNet
or such surviving entity or any parent thereof outstanding immediately after
such merger or consolidation (either by remaining outstanding or by being
converted into voting securities of the surviving entity or parent thereof), or
(ii) a merger or consolidation




                                      5
<PAGE>   6
effected to implement a recapitalization of PageNet, or similar transaction, in
which no Person is or becomes the Beneficial Owner, directly or indirectly, of
securities of PageNet representing 35% or more of the combined voting power of
PageNet's then outstanding securities (not including in the securities
Beneficially Owned by such Person any securities acquired directly from
PageNet); or

                 (d) the shareowners of PageNet approve a plan of complete
liquidation or dissolution of PageNet or there is consummated an agreement for
the sale or disposition by PageNet of all or substantially all of PageNet's
assets, other than a sale or disposition by PageNet of all or substantially all
of PageNet's assets to an entity, at least 65% of the combined voting power of
the outstanding securities of which are owned by shareowners of PageNet in
substantially the same proportions as their ownership of PageNet immediately
prior to such sale.

         Notwithstanding the foregoing, a "Change of Control" shall not be
deemed to have occurred by virtue of the consummation of any transaction or
series of integrated transactions immediately following which the record
holders of the Common Stock of PageNet immediately prior to such transaction or
series of transactions continue to have substantially the same proportionate
ownership in an entity which owns all or substantially all of the assets of
PageNet immediately following such transaction or series of transactions.

         For purposes of this Section 10, (a) "Person" shall mean any person or
entity other than (1) any employee plan established by PageNet, (2) PageNet or
any of its affiliates (as defined in Rule 12b-2 promulgated under the
Securities Exchange Act of 1934, as amended (2) (the "Exchange Act")), (3) an
underwriter temporarily holding securities pursuant to an offering of such
securities, or (4) a corporation owned, directly or indirectly, by shareowners
of PageNet in substantially the same proportions as their ownership of PageNet
and (b) "Beneficial Owner" shall have the meaning set forth in Rule 12d-3 under
the Exchange Act.

         11.     TERMINATION OR AMENDMENT OF PLAN. The Board may at any time
suspend or terminate the Plan, or make such changes in or additions to the Plan
as it deems advisable without further action on the part of the shareowners of
the Company, provided:

                 (a) that no such termination or amendment will adversely
affect or impair any then outstanding option or any shares at the time subject
to options without the consent of the optionee holding such option; and

                 (b) that any such amendment which requires shareowner approval
in order to comply with applicable provisions of the Code, rules promulgated
pursuant to Section 16 of the Exchange Act, applicable state law, or the
National Association of Securities Dealers or exchange listing requirements
will be subject to approval by the shareowners of PageNet within one year from
the effective date of such amendment and will be null and void if such approval
is not obtained.




                                      6
<PAGE>   7
         12.     MISCELLANEOUS PROVISIONS.

                 (a) GOVERNING LAW. The validity, construction, interpretation,
administration and effect of the Plan, and of its rules and regulations, and
rights relating to the Plan, will be governed by the substantive laws, but not
the choice of law rules, of the State of Delaware.

                 (b) NO GUARANTEE OF EMPLOYMENT. Neither the Plan, not any
action taken hereunder, including the granting of options, shall be construed
as giving any employee any right to continue to be employed by the Company, and
the right to terminate the employment of any such employee is hereby
specifically reserved.




                                      7